一、什么是Hash表
要想知道什么是哈希表，那得先了解哈希函數(shù)
哈希函數(shù)
對比之前博客討論的二叉排序樹 二叉平衡樹 紅黑樹 B B+樹，它們的查找都是先從根節(jié)點進行查找，從節(jié)點取出數(shù)據(jù)或索引與查找值進行比較。那么，有沒有一種函數(shù)H，根據(jù)這個函數(shù)和查找關(guān)鍵字key，可以直接確定查找值所在位置，而不需要一個個比較。這樣就“預(yù)先知道”key所在的位置，直接找到數(shù)據(jù)，提升效率。
即
*地址index=H(key)
說白了，hash函數(shù)就是根據(jù)key計算出應(yīng)該存儲地址的位置，而哈希表是基于哈希函數(shù)建立的一種查找表
二、哈希函數(shù)的構(gòu)造方法
根據(jù)前人經(jīng)驗，統(tǒng)計出如下幾種常用hash函數(shù)的構(gòu)造方法：
-
直接定制法
哈希函數(shù)為關(guān)鍵字的線性函數(shù)如 H（key）=a*key+b
這種構(gòu)造方法比較簡便，均勻，但是有很大限制，僅限于地址大小=關(guān)鍵字集合的情況
使用舉例：
假設(shè)需要統(tǒng)計中國人口的年齡分布，以10為最小單元。今年是2018年，那么10歲以內(nèi)的分布在2008-2018，20歲以內(nèi)的分布在1998-2008……假設(shè)2018代表2018-2008直接的數(shù)據(jù)，那么關(guān)鍵字應(yīng)該是2018，2008，1998……
那么可以構(gòu)造哈希函數(shù)H（key）=（2018-key）/10=201-key/10
那么hash表建立如下
| index | key | 年齡 | 人數(shù)（假設(shè)數(shù)據(jù)） |
|---|---|---|---|
| 0 | 2018 | 0-10 | 200W |
| 1 | 2008 | 10-20 | 250W |
| 2 | 1998 | 20-30 | 253W |
| 3 | 1988 | 30-40 | 300W |
| …… |
-
數(shù)字分析法
假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字key都是由s位數(shù)字組成（k1, k2 , … … , kn）,分析key中的全體數(shù)據(jù)，并從中提取分布均勻的若干位或他們的組合構(gòu)成全體
使用舉例
我們知道身份證號是有規(guī)律的，現(xiàn)在我們要存儲一個班級學(xué)生的身份證號碼，假設(shè)這個班級的學(xué)生都出生在同一個地區(qū)，同一年，那么他們的身份證的前面數(shù)位都是相同的，那么我們可以截取后面不同的幾位存儲，假設(shè)有5位不同，那么就用這五位代表地址。
H（key）=key%100000
此種方法通常用于數(shù)字位數(shù)較長的情況，必須數(shù)字存在一定規(guī)律，其必須知道數(shù)字的分布情況，比如上面的例子，我們事先知道這個班級的學(xué)生出生在同一年，同一個地區(qū)。 -
平方取中法
如果關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻率很高的現(xiàn)象，可以先求關(guān)鍵字的平方值，通過平方擴大差異，而后取中間數(shù)位作為最終存儲地址。
使用舉例
比如key=1234 1234^2=1522756 取227作hash地址
比如key=4321 4321^2=18671041 取671作hash地址
這種方法適合事先不知道數(shù)據(jù)并且數(shù)據(jù)長度較小的情況 -
折疊法
如果數(shù)字的位數(shù)很多，可以將數(shù)字分割為幾個部分，取他們的疊加和作為hash地址
使用舉例
比如key=123 456 789
我們可以存儲在61524，取末三位，存在524的位置
該方法適用于數(shù)字位數(shù)較多且事先不知道數(shù)據(jù)分布的情況
除留余數(shù)法用的較多
H（key）=key MOD p （p<=m m為表長）
很明顯，如何選取p是個關(guān)鍵問題。
比如我們存儲3 6 9，那么p就不能取3
因為 3 MOD 3 == 6 MOD 3 == 9 MOD 3
p應(yīng)為不大于m的質(zhì)數(shù)或是不含20以下的質(zhì)因子的合數(shù)，這樣可以減少地址的重復(fù)（沖突）
比如key = 7，39，18，24，33，21時取表長m為9 p為7 那么存儲如下
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| key | 7 | 21（沖突后移） | 24 | 39 | 18（沖突后移） | 33(沖突后移） |
-
隨機數(shù)法
H(key) =Random(key) 取關(guān)鍵字的隨機函數(shù)值為它的散列地址
hash函數(shù)設(shè)計的考慮因素
1.計算散列地址所需要的時間（即hash函數(shù)本身不要太復(fù)雜）
2.關(guān)鍵字的長度
3.表長
4.關(guān)鍵字分布是否均勻，是否有規(guī)律可循
5.設(shè)計的hash函數(shù)在滿足以上條件的情況下盡量減少沖突
三、哈希沖突
即不同key值產(chǎn)生相同的地址，H(key1)=H(key2)
比如我們上面說的存儲3 6 9，p取3是
3 MOD 3 == 6 MOD 3 == 9 MOD 3
此時3 6 9都發(fā)生了hash沖突
哈希沖突的解決方案
不管hash函數(shù)設(shè)計的如何巧妙，總會有特殊的key導(dǎo)致hash沖突，特別是對動態(tài)查找表來說。
hash函數(shù)解決沖突的方法有以下幾個常用的方法
- 1.開放定制法
- 2.鏈地址法
- 3.公共溢出區(qū)法
建立一個特殊存儲空間，專門存放沖突的數(shù)據(jù)。此種方法適用于數(shù)據(jù)和沖突較少的情況。 - 4.再散列法
準(zhǔn)備若干個hash函數(shù)，如果使用第一個hash函數(shù)發(fā)生了沖突，就使用第二個hash函數(shù)，第二個也沖突，使用第三個……
重點了解一下開放定制法和鏈地址法
開放定制法
首先有一個H（key）的哈希函數(shù)
如果H(key1)=H(keyi)
那么keyi存儲位置H=(H(key) + di ) MOD m （m為表長）
有三種取法
- 1）線性探測再散列
di = c*i - 2）平方探測再散列
di=12,-1^2, 2^2, -2^2 …… - 3）隨機探測在散列（雙探測再散列）
di 是一組偽隨機數(shù)列
注意
增量di應(yīng)該具有以下特點（完備性）：產(chǎn)生的Hi（地址）均不相同，且所產(chǎn)生的s（m-1）個Hi能覆蓋hash表中的所有地址
平方探測時表長m必須為4j+3的質(zhì)數(shù)（平方探測表長有限制）
隨機探測時m和di沒有公因子（隨機探測di有限制）
三種開放定址法解決沖突方案的例子
廢話不多說，上例子就明白了
有一組數(shù)據(jù)
19 01 23 14 55 68 11 86 37要存儲在表長11的數(shù)組中，其中H（key）=key MOD 11
那么按照上面三種解決沖突的方法，存儲過程如下：
（表格解釋：從前向后插入數(shù)據(jù)，如果插入位置已經(jīng)占用，發(fā)生沖突，沖突的另起一行，計算地址，直到地址可用，后面沖突的繼續(xù)向下另起一行。最終結(jié)果取最上面的數(shù)據(jù)（因為是最“占座”的數(shù)據(jù)））
線性探測再散列:
我們?nèi)i=1，即沖突后存儲在沖突后一個位置，如果仍然沖突繼續(xù)向后
| index | 0 | 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 | |||||||||
| 最終存儲結(jié)果 | 55 | 1 | 23 | 14 | 68 | 11 | 37 | 19 | 86 |
平方探測再散列 :
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| key | 55 | 1 | 68 | 14 | 19 | 86 | |||||
| 23沖突 | H（23）+1 | ||||||||||
| H（68）-1沖突 | 68沖突 | H（68）+1沖突 | H（68）+4 | ||||||||
| 11沖突 | H（11）+1沖突 | H（11）-1 | |||||||||
| 最終存儲結(jié)果 | 55 | 1 | 23 | 14 | 37 | 68 | 19 | 86 | 11 |
隨機探測在散列（雙探測再散列）：
發(fā)生沖突后 H（key）‘=(H(key)+di)MOD m 在該例子中 H（key）=key MOD 11 我們?nèi)i=key MOD 10 +1 則有如下結(jié)果：
| index | 0 | 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沖突 | ||||||||
| 最終存儲結(jié)果 | 55 | 1 | 68 | 14 | 23 | 11 | 37 | 19 | 86 |
鏈地址法
產(chǎn)生hash沖突后在存儲數(shù)據(jù)后面加一個指針，指向后面沖突的數(shù)據(jù)
上面的例子，用鏈地址法則是下面這樣：
四、hash表的查找
查找過程和造表過程一致，假設(shè)采用開放定址法處理沖突，則查找過程為：
對于給定的key，計算hash地址index = H（key）
如果數(shù)組arr【index】的值為空 則查找不成功
如果數(shù)組arr【index】== key 則查找成功
否則 使用沖突解決方法求下一個地址，直到arr【index】== key或者 arr【index】==null
hash表的查找效率
決定hash表查找的ASL因素：
1）選用的hash函數(shù)
2）選用的處理沖突的方法
3）hash表的飽和度，裝載因子 α=n/m(n表示實際裝載數(shù)據(jù)長度 m為表長)
一般情況，假設(shè)hash函數(shù)是均勻的，則在討論ASL時可以不考慮它的因素
hash表的ASL是處理沖突方法和裝載因子的函數(shù)
前人已經(jīng)證明，查找成功時如下結(jié)果：
可以看到無論哪個函數(shù)，裝載因子越大，平均查找長度越大，那么裝載因子α越小越好？也不是，就像100的表長只存一個數(shù)據(jù)，α是小了，但是空間利用率不高啊，這里就是時間空間的取舍問題了。通常情況下，認(rèn)為α=0.75是時間空間綜合利用效率最高的情況。
上面的這個表可是特別有用的。假設(shè)我現(xiàn)在有10個數(shù)據(jù)，想使用鏈地址法解決沖突，并要求平均查找長度<2
那么有1+α/2 <2
α<2
即 n/m<2 (n=10)
m>10/2
m>5 即采用鏈地址法，使得平均查找長度< 2 那么m>5
之前我的博客討論過各種樹的平均查找長度，他們都是基于存儲數(shù)據(jù)n的函數(shù)，而hash表不同，他是基于裝載因子的函數(shù)，也就是說，當(dāng)數(shù)據(jù)n增加時，我可以通過增加表長m，以維持裝載因子不變，確保ASL不變。
那么hash表的構(gòu)造應(yīng)該是這樣的：
五、hash表的刪除
首先鏈地址法是可以直接刪除元素的，但是開放定址法是不行的，拿前面的雙探測再散列來說，假如我們刪除了元素1，將其位置置空，那 23就永遠找不到了。正確做法應(yīng)該是刪除之后置入一個原來不存在的數(shù)據(jù)，比如-1
————————————————
版權(quán)聲明：本文為CSDN博主「洌冰」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/u011109881/article/details/80379505
