一、什么是Hash表

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

哈希函數(shù):

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

即 地址index=H（key）

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

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

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

直接定制法

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

這種構(gòu)造方法比較簡(jiǎn)便，均勻，但是有很大限制，僅限于地址大小=關(guān)鍵字集合的情況

使用舉例：

假設(shè)需要統(tǒng)計(jì)中國(guó)人口的年齡分布，以10為最小單元。今年是2018年，那么10歲以?xún)?nèi)的分布在2008-2018，20歲以?xún)?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)鍵字集合中的每個(gè)關(guān)鍵字key都是由s位數(shù)字組成（k1,k2,……,knk1,k2,……,kn）,分析key中的全體數(shù)據(jù)，并從中提取分布均勻的若干位或他們的組合構(gòu)成全體

使用舉例

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

H（key）=key%100000

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

平方取中法

如果關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻率很高的現(xiàn)象，可以先求關(guān)鍵字的平方值，通過(guò)平方擴(kuò)大差異，而后取中間數(shù)位作為最終存儲(chǔ)地址。

使用舉例

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

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

這種方法適合事先不知道數(shù)據(jù)并且數(shù)據(jù)長(zhǎng)度較小的情況

折疊法
如果數(shù)字的位數(shù)很多，可以將數(shù)字分割為幾個(gè)部分，取他們的疊加和作為hash地址
使用舉例
比如key=123 456 789
我們可以存儲(chǔ)在61524，取末三位，存在524的位置
該方法適用于數(shù)字位數(shù)較多且事先不知道數(shù)據(jù)分布的情況

除留余數(shù)法用的較多
H（key）=key MOD p （p<=m m為表長(zhǎng)）
很明顯，如何選取p是個(gè)關(guān)鍵問(wèn)題。

使用舉例

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

因?yàn)?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時(shí)取表長(zhǎng)m為9 p為7 那么存儲(chǔ)如下

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

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

1.計(jì)算散列地址所需要的時(shí)間（即hash函數(shù)本身不要太復(fù)雜）
2.關(guān)鍵字的長(zhǎng)度
3.表長(zhǎng)
4.關(guān)鍵字分布是否均勻，是否有規(guī)律可循
5.設(shè)計(jì)的hash函數(shù)在滿(mǎn)足以上條件的情況下盡量減少?zèng)_突

三、哈希沖突

即不同key值產(chǎn)生相同的地址，H（key1）=H（key2）
比如我們上面說(shuō)的存儲(chǔ)3 6 9，p取3是
3 MOD 3 == 6 MOD 3 == 9 MOD 3
此時(shí)3 6 9都發(fā)生了hash沖突

哈希沖突的解決方案

不管hash函數(shù)設(shè)計(jì)的如何巧妙，總會(huì)有特殊的key導(dǎo)致hash沖突，特別是對(duì)動(dòng)態(tài)查找表來(lái)說(shuō)。

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

1.開(kāi)放定制法

2.鏈地址法

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

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

4.再散列法

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

重點(diǎn)了解一下開(kāi)放定制法和鏈地址法

開(kāi)放定制法

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

如果H（key1）=H（keyi）

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

注意

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

* 平方探測(cè)時(shí)表長(zhǎng)m必須為4j+3的質(zhì)數(shù)（平方探測(cè)表長(zhǎng)有限制）

* 隨機(jī)探測(cè)時(shí)m和di沒(méi)有公因子（隨機(jī)探測(cè)di有限制）

三種開(kāi)放定址法解決沖突方案的例子

有一組數(shù)據(jù)

19 01 23 14 55 68 11 86 37要存儲(chǔ)在表長(zhǎng)11的數(shù)組中，其中H（key）=key MOD 11

那么按照上面三種解決沖突的方法，存儲(chǔ)過(guò)程如下：

（表格解釋?zhuān)簭那跋蚝蟛迦霐?shù)據(jù)，如果插入位置已經(jīng)占用，發(fā)生沖突，沖突的另起一行，計(jì)算地址，直到地址可用，后面沖突的繼續(xù)向下另起一行。最終結(jié)果取最上面的數(shù)據(jù)（因?yàn)槭亲睢罢甲钡臄?shù)據(jù)））

線性探測(cè)再散列

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

平方探測(cè)再散列

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

鏈地址法

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

四、hash表的查找

查找過(guò)程和造表過(guò)程一致，假設(shè)采用開(kāi)放定址法處理沖突，則查找過(guò)程為：

對(duì)于給定的key，計(jì)算hash地址index = H（key）

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

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

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

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

上面的這個(gè)表可是特別有用的。假設(shè)我現(xiàn)在有10個(gè)數(shù)據(jù)，想使用鏈地址法解決沖突，并要求平均查找長(zhǎng)度<2

那么有1+α/2 <2

α<2

即 n/m<2 (n=10)

m>10/2

m>5 即采用鏈地址法，使得平均查找長(zhǎng)度< 2 那么m>5

之前我的博客討論過(guò)各種樹(shù)的平均查找長(zhǎng)度，他們都是基于存儲(chǔ)數(shù)據(jù)n的函數(shù)，而hash表不同，他是基于裝載因子的函數(shù)，也就是說(shuō)，當(dāng)數(shù)據(jù)n增加時(shí)，我可以通過(guò)增加表長(zhǎng)m，以維持裝載因子不變，確保ASL不變。

那么hash表的構(gòu)造應(yīng)該是這樣的：

五、hash表的刪除

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