資料結構 Hash表解讀（哈希表）一、什麼是Hash表要想知道什麼是哈希表，那得先了解哈希函數 哈希函數

參考連結：https://blog.csdn.net/u011109881/article/details/80379505

一、什麼是Hash表

要想知道什麼是哈希表，那得先了解哈希函數

哈希函數

對比之前部落格讨論的二叉排序樹 二叉平衡樹 紅黑樹 B B+樹，它們的查找都是先從根節點進行查找，從節點取出資料或索引與查找值進行比較。那麼，有沒有一種函數H，根據這個函數和查找關鍵字key，可以直接确定查找值所在位置，而不需要一個個比較。這樣就**“預先知道”**key所在的位置，直接找到資料，提升效率。

即

位址index=H（key）

說白了，hash函數就是根據key計算出應該存儲位址的位置，而哈希表是基于哈希函數建立的一種查找表

二、哈希函數的構造方法

根據前人經驗，統計出如下幾種常用hash函數的構造方法：

直接定制法

哈希函數為關鍵字的線性函數如 H（key）=a*key+b

這種構造方法比較簡便，均勻，但是有很大限制，僅限于位址大小=關鍵字集合的情況

使用舉例：

假設需要統計中國人口的年齡分布，以10為最小單元。今年是2018年，那麼10歲以内的分布在2008-2018，20歲以内的分布在1998-2008……假設2018代表2018-2008直接的資料，那麼關鍵字應該是2018，2008，1998……

那麼可以構造哈希函數H（key）=（2018-key）/10=201-key/10

那麼hash表建立如下

index	key	年齡	人數（假設資料）
2018	0-10	200W
1	2008	10-20	250W
2	1998	20-30	253W
3	1988	30-40	300W
……

數字分析法

假設關鍵字集合中的每個關鍵字key都是由s位數字組成（k1,k2,……,knk_1,k_2,……,k_nk1​,k2​,……,kn​）,分析key中的全體資料，并從中提取分布均勻的若幹位或他們的組合構成全體

使用舉例

我們知道身份證号是有規律的，現在我們要存儲一個班級學生的身份證号碼，假設這個班級的學生都出生在同一個地區，同一年，那麼他們的身份證的前面數位都是相同的，那麼我們可以截取後面不同的幾位存儲，假設有5位不同，那麼就用這五位代表位址。

H（key）=key%100000

此種方法通常用于數字位數較長的情況，必須數字存在一定規律，其必須知道數字的分布情況，比如上面的例子，我們事先知道這個班級的學生出生在同一年，同一個地區。

平方取中法

如果關鍵字的每一位都有某些數字重複出現頻率很高的現象，可以先求關鍵字的平方值，通過平方擴大差異，而後取中間數位作為最終存儲位址。

使用舉例

比如key=1234 1234^2=1522756 取227作hash位址

比如key=4321 4321^2=18671041 取671作hash位址

這種方法适合事先不知道資料并且資料長度較小的情況

折疊法

如果數字的位數很多，可以将數字分割為幾個部分，取他們的疊加和作為hash位址

使用舉例

比如key=123 456 789

我們可以存儲在61524，取末三位，存在524的位置

該方法适用于數字位數較多且事先不知道資料分布的情況

除留餘數法用的較多

H（key）=key MOD p （p<=m m為表長）

很明顯，如何選取p是個關鍵問題。

使用舉例

比如我們存儲3 6 9，那麼p就不能取3

因為 3 MOD 3 == 6 MOD 3 == 9 MOD 3

p應為不大于m的質數或是不含20以下的質因子的合數，這樣可以減少位址的重複（沖突）

比如key = 7，39，18，24，33，21時取表長m為9 p為7 那麼存儲如下

index	1	2	3	4	5	6	7	8
key	7	21（沖突後移）	24	4	18（沖突後移）	33沖突後移）

**随機數法** H（key） =Random（key） 取關鍵字的随機函數值為它的散列位址

hash函數設計的考慮因素

1.計算散列位址所需要的時間（即hash函數本身不要太複雜）

2.關鍵字的長度

3.表長

4.關鍵字分布是否均勻，是否有規律可循

5.設計的hash函數在滿足以上條件的情況下盡量減少沖突

三、哈希沖突

即不同key值産生相同的位址，H（key1）=H（key2）

比如我們上面說的存儲3 6 9，p取3是

3 MOD 3 == 6 MOD 3 == 9 MOD 3

此時3 6 9都發生了hash沖突

哈希沖突的解決方案

不管hash函數設計的如何巧妙，總會有特殊的key導緻hash沖突，特别是對動态查找表來說。

hash函數解決沖突的方法有以下幾個常用的方法

1.開放定制法

2.鍊位址法

3.公共溢出區法

建立一個特殊存儲空間，專門存放沖突的資料。此種方法适用于資料和沖突較少的情況。

4.再散列法

準備若幹個hash函數，如果使用第一個hash函數發生了沖突，就使用第二個hash函數，第二個也沖突，使用第三個……

重點了解一下開放定制法和鍊位址法

開放定制法

首先有一個H（key）的哈希函數

如果H（key1）=H（keyi）

那麼keyi存儲位置Hi=(H(key)+di)MODmH_i=(H(key)+d_i)MOD mHi​=(H(key)+di​)MODmm為表長

did_idi​有三種取法

1）線性探測再散列

di=c∗id_i=c*idi​=c∗i

2）平方探測再散列

di=12,−12,22,−22d_i=1^2,-1^2,2^2,-2^2di​=12,−12,22,−22……

3）随機探測在散列（雙探測再散列）

did_idi​是一組僞随機數列

注意

增量di應該具有以下特點（完備性）：産生的Hi（位址）均不相同，且所産生的s（m-1）個Hi能覆寫hash表中的所有位址

• 平方探測時表長m必須為4j+3的質數（平方探測表長有限制）

• 随機探測時m和di沒有公因子（随機探測di有限制）

  三種開放定址法解決沖突方案的例子

廢話不多說，上例子就明白了

有一組資料

19 01 23 14 55 68 11 86 37要存儲在表長11的數組中，其中H（key）=key MOD 11

那麼按照上面三種解決沖突的方法，存儲過程如下：

（表格解釋：從前向後插入資料，如果插入位置已經占用，發生沖突，沖突的另起一行，計算位址，直到位址可用，後面沖突的繼續向下另起一行。最終結果取最上面的資料（因為是最“占座”的資料））

線性探測再散列

我們取di=1，即沖突後存儲在沖突後一個位置，如果仍然沖突繼續向後

index	1	2	3	4	5	6	7	8	9	10
key	55	1	14	19	86
23沖突	23
68沖突	68沖突	68
11沖突	11沖突	11沖突	11沖突	11沖突	11
37沖突	37沖突	37
最終存儲結果	55	1	23	14	68	11	37	19	86

**平方探測再散列**

index	1	2	3	4	5	6	7	8	9	10
key	55	1	14	37	19	86
23沖突	H（23）+1
H（68）-1沖突	68沖突	H（68）+1沖突	H（68）+4
11沖突	H（11）+1沖突	H（11）-1
最終存儲結果	55	1	23	14	37	68	19	86	11

**随機探測在散列（雙探測再散列）** 發生沖突後 H（key）‘=(H(key)+di)MOD m 在該例子中 H（key）=key MOD 11 我們取di=key MOD 10 +1 則有如下結果：

index	1	2	3	4	5	6	7	8	9	10
key	55	1	68	14	19	86
23沖突	H（23）+3+1
11沖突	H（11）+1+1沖突	H（11）+1+1+1+1
（H（37）+8）模11沖突	37沖突	（H（37）+8+8+8）模11	（H（37）+8+8）模11沖突
最終存儲結果	55	1	68	14	23	11	37	19	86

鍊位址法

産生hash沖突後在存儲資料後面加一個指針，指向後面沖突的資料

上面的例子，用鍊位址法則是下面這樣：

四、hash表的查找

查找過程和造表過程一緻，假設采用開放定址法處理沖突，則查找過程為：

對于給定的key，計算hash位址index = H（key）

如果數組arr【index】的值為空 則查找不成功

如果數組arr【index】== key 則查找成功

否則 使用沖突解決方法求下一個位址，直到arr【index】== key或者 arr【index】==null

hash表的查找效率

決定hash表查找的ASL因素：

1）選用的hash函數

2）選用的處理沖突的方法

3）hash表的飽和度，裝載因子 α=n/m(n表示實際裝載資料長度 m為表長)

一般情況，假設hash函數是均勻的，則在讨論ASL時可以不考慮它的因素

hash表的ASL是處理沖突方法和裝載因子的函數

前人已經證明，查找成功時如下結果：

可以看到無論哪個函數，裝載因子越大，平均查找長度越大，那麼裝載因子α越小越好？也不是，就像100的表長隻存一個資料，α是小了，但是空間使用率不高啊，這裡就是時間空間的取舍問題了。通常情況下，認為α=0.75是時間空間綜合利用效率最高的情況。

上面的這個表可是特别有用的。假設我現在有10個資料，想使用鍊位址法解決沖突，并要求平均查找長度<2

那麼有1+α/2 <2

α<2

即 n/m<2 (n=10)

m>10/2

m>5 即采用鍊位址法，使得平均查找長度< 2 那麼m>5

之前我的部落格讨論過各種樹的平均查找長度，他們都是基于存儲資料n的函數，而hash表不同，他是基于裝載因子的函數，也就是說，當資料n增加時，我可以通過增加表長m，以維持裝載因子不變，確定ASL不變。

那麼hash表的構造應該是這樣的：

五、hash表的删除

首先鍊位址法是可以直接删除元素的，但是開放定址法是不行的，拿前面的雙探測再散列來說，假如我們删除了元素1，将其位置置空，那 23就永遠找不到了。正确做法應該是删除之後置入一個原來不存在的資料，比如-1