哈希表Hashtable是計算機(jī)中最常見也最基本的數(shù)據(jù)結(jié)構(gòu)之一，但是有的CS基礎(chǔ)不扎實的學(xué)習(xí)者，其實還是對這個結(jié)構(gòu)一知半解，時時感到困惑。對于這部分朋友，不妨嘗試一種全新的方式——從創(chuàng)造者的角度，自己把這個結(jié)構(gòu)重新發(fā)明一遍。這個想法聽來奇怪，這不是更難了嗎？其實不然，重在節(jié)奏。只要把思路梳理清楚，把問題一步步分解，你會看見一條自然清晰的道路。

從發(fā)明的角度，我們只要問兩點：

(1) 我們想解決一個什么問題？

(2) 這個問題如何最好地解決？

1

動機(jī)：無處不在的查詢

在程序當(dāng)中，經(jīng)常碰到需要“查表”的時候，就是用某種形式的標(biāo)識（key），去查詢標(biāo)識對應(yīng)的相關(guān)信息（value）：

存一個用戶名到用戶信息的lookup table，時時備查

統(tǒng)計一段文字的單詞頻率: 那你就得建立一個從每個單詞到出現(xiàn)次數(shù)的對應(yīng)關(guān)系，掃描文字的時候看到哪個詞就把它的頻次+1

一個運(yùn)算上成本很高的函數(shù)f(n)，想讓已經(jīng)算過的結(jié)果不再產(chǎn)生重復(fù)勞動，那就需要一個表，存儲所有算過的n，和它們所對應(yīng)的計算結(jié)果。

這樣的“關(guān)鍵字查詢”需求在程序設(shè)計的過程中無處不在，所以我們需要一個高效的機(jī)制，來存儲key和value的對應(yīng)關(guān)系。

2

問題

任務(wù)：設(shè)計一個高效率的從key查詢對應(yīng)value的方法。

原料：由于hashtable過于基本，每個語言都會有自帶的結(jié)構(gòu)提供這個功能，不過既然我們在重新設(shè)計，只能當(dāng)這些語言自帶的的hashtable不存在。你的原料是最基本的，數(shù)組 array。

3

笨辦法

先來個最最基本的解法，一來幫助理解待解決的問題，二來可以對照出最終hashtable的優(yōu)點。

比如一種笨辦法就是把要存儲的 (key, value) 一對對直接堆放在數(shù)組里

每次查詢一個key的時候就從頭到尾掃描數(shù)組，找到key就停，都找遍了就知道沒有這個key。這個做法至少滿足了正確性，但是比較慢；因為線性掃描整個數(shù)組，里面key的總量一多時間成本就很高。

4

最簡問題：數(shù)組即查詢

回到我們的設(shè)計問題上。不過你想想，數(shù)組也算是實現(xiàn)了某種查詢——key都是0..N-1的查詢——輸入下標(biāo) i，數(shù)組 a[i] 告訴你這個下標(biāo)對應(yīng)的值。

而這也很符合我們的效率需求：查詢和修改都非?？臁．?dāng)然，這是因為數(shù)組就是連續(xù)內(nèi)存，下標(biāo)就是內(nèi)存取址，所以 0..N-1 相比于別的 key 來說，查詢尤為簡單直接。

那么接下來，我們要問的就是，如何讓任意一種形式的key都可以享有和特殊的 0..N-1 下標(biāo)查詢幾乎一樣的效率呢？一種思路是，只要想辦法高效地把key轉(zhuǎn)化為0..N-1的下標(biāo)就可以了。

5

下標(biāo)轉(zhuǎn)化: key=’a’..’z’

舉例/進(jìn)階題：比如說我們要做一個簡單的文字加密，我們事先規(guī)定加密關(guān)系 a -> x, b -> o, c -> p, …，把這個關(guān)系寫進(jìn)一個lookup table里面，以后加密的時候，就一個字母一個字母地讀原文，查出密文，這個字母就轉(zhuǎn)化好了。比如單詞 “cab” 就會變成 “pxo”。

分析：’a’..’z’ 雖然不是整數(shù) 0..N-1 吧，但是也差不多…

一種方案：當(dāng)然是把 ’a’..’z’ 依次序?qū)?yīng)到 0..25 咯

查詢?nèi)魏涡懽帜?ch 的時候，先計算出下標(biāo) i = ch - ‘a(chǎn)’，就可以訪問 a[i]，在數(shù)組中查出這個明文字母該對應(yīng)的密文了。

6

通用轉(zhuǎn)化：hash function

接著上面這個字母的例子，我們可以籠統(tǒng)地想了，剛才那個’a’..’z’對應(yīng)到0..N-1的過程，如果能對任何key做就好了。而這個對應(yīng)機(jī)制，就叫做哈希函數(shù) hash function：如果對于某種 key 類型（比如字符串）我們可以提供一個哈希函數(shù)hash，把 key 帶進(jìn)去就能輸出一個整數(shù) hash(key)，那我們可以以它為原料產(chǎn)生數(shù)組下標(biāo)。

通常我們會讓 hash(key) 大一些，當(dāng)然實際上數(shù)組空間只有N，所以取個余數(shù)，以 hash(key) % N 為最終數(shù)組下標(biāo)。比如 hash(key0) % N = 3， 那存成

當(dāng)然這只是理想的情況。如果我們觀察 ’a’..’z’ → 0..25 這個對應(yīng)，就會發(fā)現(xiàn)它有一個特殊性，就是“一個蘿卜一個坑”：字母和下標(biāo)一一對應(yīng)。但是，在一個更加一般的情形下，在 hash 函數(shù)和取余數(shù)的雙重操作下，有時候難免會出現(xiàn)“很多蘿卜都想去同一個坑”的狀況。怎么解決呢？人們通常想到兩種辦法：

“把坑挖深”：如果幾個key都對應(yīng)相同的數(shù)組下標(biāo)，那把這幾個蘿卜都堆放在這個坑里面。具體來說每個數(shù)組下標(biāo)下面掛的不是一對 (key, value)，而是一整個列表放著若干個 (key, value) ——這個列表其實就是類似我們最先提出的那個“笨辦法”。先用 key 和哈希函數(shù)找到坑，之后在坑內(nèi)查詢就退化成我們的“笨辦法”了。

“先來后到，后到的蘿卜找別的坑占去”：每個坑還是只容納一個蘿卜；如果一個蘿卜發(fā)現(xiàn)自己該去的坑已經(jīng)被占了，可以定義一套規(guī)則，幫助它找下個坑，一次次直到找到一個空的坑為止。

7

回顧與想象

以上，我們終于完成了hashtable大體框架的設(shè)計。想清楚了這些內(nèi)部原理，我們可以開始對它的運(yùn)行開始有一些想象，也作為一種回顧。

首先，查詢的基本流程如下圖所示，輸入key，通過hash function算出數(shù)組下標(biāo)，然后在這個數(shù)組下標(biāo)對應(yīng)的坑里面依次尋找這個具體的key。

在理想的情況下，hash函數(shù)可以成功地把 key 均勻地打散到數(shù)組下標(biāo)中，并且數(shù)組空間也比較充裕，從而 key 的下標(biāo)沖突不多，添加、修改、查詢元素，都可以通過哈希函數(shù)來快速定位，O(1)時間；偶爾碰見一些下標(biāo)沖突，但是頻率低、多找兩步還是能找到所需元素，那么總體平均下來還是大致認(rèn)為是常數(shù)時間。

反之，如果hash函數(shù)設(shè)計得不好，導(dǎo)致下標(biāo)沖突很多，極限情況下可能所有蘿卜都掉進(jìn)一個坑里，那弄了半天你可能還是退化成了我們最早提出的“笨辦法”?；蛘邤?shù)組空間不足，里面存的 (key, value) 特別多，那可能也會不得不發(fā)生很多下標(biāo)沖突，非常臃腫，達(dá)不到設(shè)想的效率。