一、什么是Hash表

要想知道什么是哈希表，那得先了解哈希函數(shù)

哈希函數(shù):

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

即 地址index=H（key）

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

二、哈希函數(shù)的構造方法

根據(jù)前人經(jīng)驗，統(tǒng)計出如下幾種常用hash函數(shù)的構造方法：

直接定制法

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

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

使用舉例：

假設需要統(tǒng)計中國人口的年齡分布，以10為最小單元。今年是2018年，那么10歲以內(nèi)的分布在2008-2018，20歲以內(nèi)的分布在1998-2008……假設2018代表2018-2008直接的數(shù)據(jù)，那么關鍵字應該是2018，2008，1998……

那么可以構造哈希函數(shù)H（key）=（2018-key）/10=201-key/10

那么hash表建立如下

index key 年齡 人數(shù)（假設數(shù)據(jù)）

0 2018 0-10 200W

1 2008 10-20 250W

2 1998 20-30 253W

3 1988 30-40 300W

……

數(shù)字分析法
假設關鍵字集合中的每個關鍵字key都是由s位數(shù)字組成（k1,k2,……,knk1,k2,……,kn）,分析key中的全體數(shù)據(jù)，并從中提取分布均勻的若干位或他們的組合構成全體

使用舉例

我們知道身份證號是有規(guī)律的，現(xiàn)在我們要存儲一個班級學生的身份證號碼，假設這個班級的學生都出生在同一個地區(qū)，同一年，那么他們的身份證的前面數(shù)位都是相同的，那么我們可以截取后面不同的幾位存儲，假設有5位不同，那么就用這五位代表地址。

H（key）=key%100000

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

平方取中法

如果關鍵字的每一位都有某些數(shù)字重復出現(xiàn)頻率很高的現(xià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是個關鍵問題。

使用舉例

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

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

p應為不大于m的質數(shù)或是不含20以下的質因子的合數(shù)，這樣可以減少地址的重復（沖突）

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

隨機數(shù)法
H（key） =Random（key）
取關鍵字的隨機函數(shù)值為它的散列地址

hash函數(shù)設計的考慮因素

1.計算散列地址所需要的時間（即hash函數(shù)本身不要太復雜）
2.關鍵字的長度
3.表長
4.關鍵字分布是否均勻，是否有規(guī)律可循
5.設計的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ù)設計的如何巧妙，總會有特殊的key導致hash沖突，特別是對動態(tài)查找表來說。

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

1.開放定制法

2.鏈地址法

3.公共溢出區(qū)法

建立一個特殊存儲空間，專門存放沖突的數(shù)據(jù)。此種方法適用于數(shù)據(jù)和沖突較少的情況。

4.再散列法

準備若干個hash函數(shù)，如果使用第一個hash函數(shù)發(fā)生了沖突，就使用第二個hash函數(shù)，第二個也沖突，使用第三個……

重點了解一下開放定制法和鏈地址法

開放定制法

首先有一個H（key）的哈希函數(shù)

如果H（key1）=H（keyi）

那么keyi存儲位置Hi=(H(key)+di)MODmHi=(H(key)+di)MODmm為表長

注意

增量di應該具有以下特點（完備性）：產(chǎn)生的Hi（地址）均不相同，且所產(chǎn)生的s（m-1）個Hi能覆蓋hash表中的所有地址

* 平方探測時表長m必須為4j+3的質數(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ù)向下另起一行。最終結果取最上面的數(shù)據(jù)（因為是最“占座”的數(shù)據(jù)））

線性探測再散列

我們?nèi)i=1，即沖突后存儲在沖突后一個位置，如果仍然沖突繼續(xù)向后

平方探測再散列

隨機探測在散列（雙探測再散列）
發(fā)生沖突后
H（key）‘=(H(key)+di)MOD m
在該例子中
H（key）=key MOD 11
我們?nèi)i=key MOD 10 +1
則有如下結果：

鏈地址法

產(chǎn)生hash沖突后在存儲數(shù)據(jù)后面加一個指針，指向后面沖突的數(shù)據(jù)
上面的例子，用鏈地址法則是下面這樣：

四、hash表的查找

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

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

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

如果數(shù)組arr【index】== key 則查找成功

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

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

上面的這個表可是特別有用的。假設我現(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ù)，也就是說，當數(shù)據(jù)n增加時，我可以通過增加表長m，以維持裝載因子不變，確保ASL不變。

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

五、hash表的刪除

首先鏈地址法是可以直接刪除元素的，但是開放定址法是不行的，拿前面的雙探測再散列來說，假如我們刪除了元素1，將其位置置空，那 23就永遠找不到了。正確做法應該是刪除之后置入一個原來不存在的數(shù)據(jù)，比如-1。