說來慚愧，本人在幾年前就接觸了數(shù)據(jù)結(jié)構(gòu)，對哈希表的認(rèn)識一直都比較模糊，在日常的學(xué)習(xí)工作中沒少用到這一數(shù)據(jù)結(jié)構(gòu)，比如像是python語言中的dict，或者是C++中的STL map，這段時(shí)間，我自己又重新學(xué)習(xí)了哈希表的一些設(shè)計(jì)原理，總結(jié)了一下，現(xiàn)在記錄在這里，就當(dāng)是幫助自己加深對hash的了解。
什么是哈希（Hash）表
Hash表也稱散列表，也有直接譯作哈希表，Hash表是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它同數(shù)組、鏈表以及二叉排序樹等相比較有很明顯的區(qū)別，它能夠快速定位到想要查找的記錄，而不是與表中存在的記錄的關(guān)鍵字進(jìn)行比較來進(jìn)行查找。這個(gè)源于Hash表設(shè)計(jì)的特殊性，它采用了函數(shù)映射的思想將記錄的存儲位置與記錄的關(guān)鍵字關(guān)聯(lián)起來，從而能夠很快速地進(jìn)行查找。
哈希表的使用
在這里給出來一組數(shù)據(jù)，這組數(shù)據(jù)對應(yīng)有兩列（名字/號碼），正常情況下，如果我們想要對這種類型的數(shù)據(jù)進(jìn)行存儲，像是int，string，char等數(shù)據(jù)類型是無法對這些數(shù)據(jù)進(jìn)行存儲的，
張三 13980593357
李四 15828662334
王五 13409821234
張帥 13890583472
在C語言中有一種數(shù)據(jù)類型叫做結(jié)構(gòu)體（struct），我們首先考慮的是定義一個(gè)結(jié)構(gòu)體，在結(jié)構(gòu)體中對這兩種數(shù)據(jù)進(jìn)行定義，然后再將這些聯(lián)系人的數(shù)據(jù)信息存儲在一個(gè)鏈表中，通過遍歷鏈表的方式，對每一個(gè)數(shù)據(jù)存儲單元（struct）進(jìn)行訪問和讀寫。不過這樣的一個(gè)劣勢就是，時(shí)間復(fù)雜度為O(n)，因?yàn)槲覀冃枰獙︽湵磉M(jìn)行從頭到尾的遍歷，即便是通過二分查找的方式進(jìn)行訪問查找，也只能夠?qū)r(shí)間復(fù)雜度降為O(log n).
那么有沒有一種數(shù)據(jù)結(jié)構(gòu)能夠?qū)⒉檎业臅r(shí)間復(fù)雜度進(jìn)一步降低呢？這里我們可以考慮使用哈希表（hash table）。
Hash表采用一個(gè)映射函數(shù)f :key -> address 將關(guān)鍵字映射到該記錄在表中的存儲位置，從而在想要查找該記錄時(shí)，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲位置，通常情況下，這種映射關(guān)系稱作為Hash函數(shù)，而通過Hash函數(shù)和關(guān)鍵字計(jì)算出來的存儲位置(注意這里的存儲位置只是表中的存儲位置，并不是實(shí)際的物理地址)稱作為Hash地址。比如上述例子中，假如聯(lián)系人信息采用Hash表存儲，則當(dāng)想要找到“李四”的信息時(shí)，直接根據(jù)“李四”和Hash函數(shù)計(jì)算出Hash地址即可。下面討論一下Hash表設(shè)計(jì)中的幾個(gè)關(guān)鍵問題。
哈希函數(shù)的設(shè)計(jì)
Hash函數(shù)設(shè)計(jì)的好壞直接影響到對Hash表的操作效率。
例如對上述的聯(lián)系人信息進(jìn)行存儲時(shí)，采用的Hash函數(shù)為：姓名的每個(gè)字的拼音開頭大寫字母的ASCII碼之和。
address(張三)=ASCII(Z)+ASCII(S)=90+83=173;
address(李四)=ASCII(L)+ASCII(S)=76+83=159;
address(王五)=ASCII(W)+ASCII(W)=87+87=174;
address(張帥)=ASCII(Z)+ASCII(S)=90+83=173;
假如只有這4個(gè)聯(lián)系人信息需要進(jìn)行存儲，這個(gè)Hash函數(shù)設(shè)計(jì)的很糟糕。
首先，它浪費(fèi)了大量的存儲空間。因?yàn)榧偃绮捎胏har型數(shù)組存儲聯(lián)系人信息的話，每個(gè)人的信息需要12個(gè)字節(jié)來存儲（手機(jī)號為11位，數(shù)值上為100多億，2^64 =1.844674407371 * 10^19，2^32 = 4294967296，所以需要64位也就是8個(gè)字節(jié)來存儲手機(jī)號。每個(gè)漢字占兩個(gè)字節(jié)，兩個(gè)漢字占四個(gè)字節(jié)。所以總共需要8 + 4 = 12Byte）這樣的話，至少需要開辟174*12字節(jié)的空間。然而空間利用率只有4/174，不到3%。
另外，根據(jù)Hash函數(shù)計(jì)算結(jié)果之后，address(張三)和address(張帥)具有相同的地址，這種現(xiàn)象稱作沖突，對于174個(gè)存儲空間中只需要存儲4條記錄就發(fā)生了沖突，這樣的Hash函數(shù)設(shè)計(jì)是很不合理的。所以在構(gòu)造Hash函數(shù)時(shí)應(yīng)盡量考慮關(guān)鍵字的分布特點(diǎn)來設(shè)計(jì)函數(shù)使得Hash地址隨機(jī)均勻地分布在整個(gè)地址空間當(dāng)中。
通常有以下幾種構(gòu)造Hash函數(shù)的方法：
直接定址法
取關(guān)鍵字或者關(guān)鍵字的某個(gè)線性函數(shù)作為Hash地址，即address(key) = a*key + b; 如果知道學(xué)生的學(xué)號是從2000開始，最大為4000，則可以將address(key) =key-2000作為Hash地址。
平方取中法
對關(guān)鍵字進(jìn)行平方計(jì)算，然后取結(jié)果的中間幾位作為Hash地址，假如有以下關(guān)鍵字序列{421，423，436}，平方之后的結(jié)果為{177241，178929，190096}，那么可以取中間的兩位數(shù){72，89，00}作為Hash地址。
折疊法
將關(guān)鍵字拆分成幾個(gè)部分，然后將這幾個(gè)部分組合在一起，以特定的方式進(jìn)行轉(zhuǎn)化形成Hash地址。例如假如知道某圖書的SBN號為：8903-241-23，可以將address(key)=89+03+24+12+3作為Hash地址。
除留取余法
如果知道Hash表的最大長度為m，可以取不大于m的最大質(zhì)數(shù)p，然后對關(guān)鍵字進(jìn)行取余運(yùn)算，address(key)=key % p。
在這里p的選取非常關(guān)鍵，p選擇的好的話，能夠最大程度地減少?zèng)_突，p一般取不大于m的最大質(zhì)數(shù)。
Hash表大小的確定
Hash表大小的確定非常關(guān)鍵，如果Hash表的空間遠(yuǎn)遠(yuǎn)大于最后實(shí)際存儲的記錄個(gè)數(shù)，就會(huì)造成較大的空間浪費(fèi)。如果選取小了的話，則容易造成沖突。在實(shí)際情況中，一般需要根據(jù)最終記錄存儲個(gè)數(shù)和關(guān)鍵字的分布特點(diǎn)來確定Hash表的大小。還有一種情況時(shí)可能事先不知道最終需要存儲的記錄個(gè)數(shù)，則需要?jiǎng)討B(tài)維護(hù)Hash表的容量，此時(shí)可能需要重新計(jì)算Hash地址。
沖突的解決
如果產(chǎn)生了Hash沖突，就需要辦法來解決，通常有如下兩種方法：
開放定址法
即當(dāng)一個(gè)關(guān)鍵字和另一個(gè)關(guān)鍵字發(fā)生沖突時(shí)，使用某種探測技術(shù)在Hash表中形成一個(gè)探測序列，然后沿著這個(gè)探測序列依次查找下去，當(dāng)碰到一個(gè)空的單元時(shí)，則插入其中。比較常用的探測方法有線性探測法，比如有一組關(guān)鍵字 {12，13，25，23，38，34，6，84，91}，Hash表長為14，Hash函數(shù)為address(key)=key%11 ，當(dāng)插入12，13，25時(shí)可以直接插入，而當(dāng)插入23時(shí)，地址1被占用了，因此沿著地址1依次往下探測(探測步長可以根據(jù)情況而定)，直到探測到地址4，發(fā)現(xiàn)為空，則將23插入其中。
鏈地址法
采用數(shù)組和鏈表相結(jié)合的辦法，將Hash地址相同的記錄存儲在一張線性表中，而每張表的表頭的序號即為計(jì)算得到的Hash地址。如上述例子中，采用鏈地址法形成的Hash表存儲表示為：
Hash表的平均查找長度
Hash表的平均查找長度包括查找成功時(shí)候的平均查找長度和查找失敗時(shí)候的平均查找長度。
查找不成功時(shí)的平均查找長度相當(dāng)于在表中查找元素不成功時(shí)的平均比較次數(shù)，可以理解為向表中插入某個(gè)元素，該元素在每個(gè)位置都有可能，然后計(jì)算出在每個(gè)位置能夠插入時(shí)需要比較的次數(shù)，再除以表長即為查找不成功時(shí)的平均查找長度。
例
這里我們將關(guān)鍵字序列{7,8,30,11,18,9,14}散列存儲到散列表中。散列表的存儲空間是一個(gè)下標(biāo)從0開始的一維數(shù)組，長度為10，即{0,1,2,3,4,5,6,7,8,9}.散列函數(shù)為：H(key) = (key * 3) % 7，處理沖突采用了線性探測再散列法。
Step 1 求散列表
H(7) = (7*3)%7 = 0
H(8) = (8*3)%7 = 0
H(30) = (30*3)%7 = 6
H(11) = (11*3)%7 = 5
H(18) = (18*3)%7 = 5
H(9) = (9*3)%7 = 6
H(14) = (14*3)%7 = 0
按關(guān)鍵字序列順序依次向哈希表中填入，發(fā)生沖突后按照“線性探測”探測到第一個(gè)空位置填入。
H(7) = 0，key = 7應(yīng)插在第0個(gè)位置，因?yàn)榈?個(gè)位置為空，可以直接插入。
H(8) = 3，key = 8應(yīng)插在第3個(gè)位置，因?yàn)榈?個(gè)位置為空，可以直接插入。
H(30) = 6，key = 30應(yīng)插在第6個(gè)位置，因?yàn)榈?個(gè)位置為空，可以直接插入。
H(11) = 5，key = 11應(yīng)插在第5個(gè)位置，因?yàn)榈?個(gè)位置為空，可以直接插入。
H(18) = 5，key = 18應(yīng)插在第5個(gè)位置，但是第5個(gè)位置已經(jīng)被key=11占據(jù)了，所以往后挪一位到第6個(gè)位置，但是第6個(gè)位置被key=30占據(jù)了，再往后挪一位到第7個(gè)位置，這個(gè)位置是空的，所以key=18就插到這個(gè)位置
H(9) = 6，key = 9應(yīng)插在第6個(gè)位置，但是第6個(gè)位置已經(jīng)被key = 30占據(jù)，所以需要往后挪一位到第7個(gè)位置，但是第7個(gè)位置已經(jīng)被key = 18占據(jù)，所以再往后挪移到第8個(gè)位置，這個(gè)位置是空的，所以key = 9就插到這個(gè)位置。
H(14) = 0，key = 14應(yīng)插在第0個(gè)位置，但第0個(gè)位置已被key=7占據(jù)，所以往后挪移一位到第1個(gè)位置，這個(gè)位置是空的，所以key=14就插到這個(gè)位置。
最終的插入結(jié)果如下表所示：
address 0 1 2 3 4 5 6 7 8 9
key 7 14 8 11 30 18 9
Step2 求查找成功的平均長度
查找7，H(7) = 0，在0的位置，一下子就找到了7，查找長度為1。
查找8，H(8) = 3，在3的位置，一下子就找到了8，查找長度為1。
查找30，H(30) = 6，在6的位置，一下子就找到了30，查找長度為1。
查找11，H(11) = 5，在5的位置，一下子就找到了11，查找長度為1。
查找18，H(18) = 5，第一次在5的位置沒有找到18，第二次往后挪移一位到6的位置，仍沒有找到，第三次再往后挪移一位到7的位置，找到了，查找長度為3。
查找9，H(9) = 6，第一次在6的位置沒找到9，第二次往后挪移一位到7的位置，仍沒有找到，第三次再往后挪移一位到8的位置，找到了，查找長度為3.
查找14，H(14) = 0，第一次在0的位置沒找到14，第二次往后挪移一位到1的位置，找到了，查找長度為2。
所以，查找成功的平均查找長度為(1 + 1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7
Step3 求查找不成功的平均查找長度
查找不成功，說明要查找的數(shù)字肯定不在上述的散列表中。
因?yàn)檫@里哈希函數(shù)的模為7，所以要查找的數(shù)的初始地址只可能位于0~6的位置上。
地址0，到第一個(gè)關(guān)鍵字為空的地址2需要比較3次，因此查找不成功的次數(shù)為3。比如要查找的數(shù)為28，H(28) = (28 * 3) % 7 = 0。即28對應(yīng)的地址是0，由于存放在0位置的數(shù)是7，所以往后挪移一位，發(fā)現(xiàn)在1位置存放的數(shù)是14，繼續(xù)往后挪一位，發(fā)現(xiàn)位置2上沒有數(shù)。至此就知道28不在這個(gè)哈希表里，即查找28失敗。
地址1，到第一個(gè)關(guān)鍵字為空的地址2需要比較2次，因此查找不成功的次數(shù)為2。
地址2，到第一個(gè)關(guān)鍵字為空的地址2需要比較1次，因此查找不成功的次數(shù)為1。
地址3，到第一個(gè)關(guān)鍵字為空的地址4需要比較2次，因此查找不成功的次數(shù)為2。
地址4，到第一個(gè)關(guān)鍵字為空的地址4需要比較1次，因此查找不成功的次數(shù)為1。
地址5，到第一個(gè)關(guān)鍵字為空的地址9需要比較5次，因此查找不成功的次數(shù)為5。
比如要查找的數(shù)為4，H(4) = (4 * 3) % 7 = 5，所以從地址5開始查找，最終發(fā)現(xiàn)地址5、地址6、地址7、地址8上存放的數(shù)都不是5，并且地址9的位置上沒放數(shù)據(jù)，至此可知5不在這個(gè)哈希表里。
地址6，到第一個(gè)關(guān)鍵字為空的地址9需要比較4次，因此查找不成功的次數(shù)為4。
所以，查找不成功的平均查找長度為（3 + 2 + 1 + 2 + 1 + 5 + 4）/ 7 = 18 / 7
作者：Paul 5/28/2019
