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

從發明的角度，我們只要問兩點：

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

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

1

動機：無處不在的查詢

在程序當中，經常碰到需要“查表”的時候，就是用某種形式的標識（key），去查詢標識對應的相關信息（value）：

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

統計一段文字的單詞頻率: 那你就得建立一個從每個單詞到出現次數的對應關系，掃描文字的時候看到哪個詞就把它的頻次+1

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

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

2

問題

任務：設計一個高效率的從key查詢對應value的方法。

原料：由于hashtable過于基本，每個語言都會有自帶的結構提供這個功能，不過既然我們在重新設計，只能當這些語言自帶的的hashtable不存在。你的原料是最基本的，數組 array。

3

笨辦法

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

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

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

4

最簡問題：數組即查詢

回到我們的設計問題上。不過你想想，數組也算是實現了某種查詢——key都是0..N-1的查詢——輸入下標 i，數組 a[i] 告訴你這個下標對應的值。

而這也很符合我們的效率需求：查詢和修改都非常快。當然，這是因為數組就是連續內存，下標就是內存取址，所以 0..N-1 相比于別的 key 來說，查詢尤為簡單直接。

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

5

下標轉化: key=’a’..’z’

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

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

一種方案：當然是把 ’a’..’z’ 依次序對應到 0..25 咯

查詢任何小寫字母 ch 的時候，先計算出下標 i = ch - ‘a’，就可以訪問 a[i]，在數組中查出這個明文字母該對應的密文了。

6

通用轉化：hash function

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

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

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

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

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

7

回顧與想象

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

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

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

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