一译荞、什么是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表建立如下

數(shù)字分析法
假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字key都是由s位數(shù)字組成（k 1 , k 2 , … … , k n k_1,k_2,……,k_nk
1

,k
2

,……,k
n

）,分析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 那么存儲如下

三墩虹、哈希沖突

即不同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ù)墅冷，第二個也沖突纯路，使用第三個……
重點了解一下開放定制法和鏈地址法

開放定制法

注意
增量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ù)向后

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

鏈地址法
產(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就永遠(yuǎn)找不到了。正確做法應(yīng)該是刪除之后置入一個原來不存在的數(shù)據(jù)硕勿，比如-1