前言

本節(jié)課程思維導(dǎo)圖：

Word 的單詞拼寫(xiě)檢查功能，雖然很小但卻非常實(shí)用。你有沒(méi)有想過(guò)，這個(gè)功能是如何實(shí)現(xiàn)的呢？其實(shí)啊，一點(diǎn)兒都不難。只要你學(xué)完今天的內(nèi)容，散列表（Hash Table）。你就能像微軟 Office 的工程師一樣，輕松實(shí)現(xiàn)這個(gè)功能。

散列思想

散列表的英文叫“Hash Table”，我們平時(shí)也叫它“哈希表”或者“Hash 表”。你一定也經(jīng)常聽(tīng)過(guò)它，但是你是不是真的理解這種數(shù)據(jù)結(jié)構(gòu)呢？
散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪(fǎng)問(wèn)數(shù)據(jù)的特性，所以散列表其實(shí)就是數(shù)組的一種擴(kuò)展，由數(shù)組演化而來(lái)?？梢哉f(shuō)，如果沒(méi)有數(shù)組，就沒(méi)有散列表。
我用一個(gè)例子來(lái)解釋一下。假如我們有 89 名選手參加學(xué)校運(yùn)動(dòng)會(huì)。為了方便記錄成績(jī)，每個(gè)選手胸前都會(huì)貼上自己的參賽號(hào)碼。假設(shè)校長(zhǎng)說(shuō)，參賽編號(hào)不能設(shè)置得這么簡(jiǎn)單，要加上年級(jí)、班級(jí)這些更詳細(xì)的信息，所以我們把編號(hào)的規(guī)則稍微修改了一下，用 6 位數(shù)字來(lái)表示。比如 051167，其中，前兩位 05 表示年級(jí)，中間兩位 11 表示班級(jí)，最后兩位還是原來(lái)的編號(hào) 1 到 89。這個(gè)時(shí)候我們?cè)撊绾未鎯?chǔ)選手信息，才能夠支持通過(guò)編號(hào)來(lái)快速查找選手信息呢？
我們可以把這 89 名選手的信息放在數(shù)組里。盡管我們不能直接把編號(hào)作為數(shù)組下標(biāo)，但我們可以截取參賽編號(hào)的后兩位作為數(shù)組下標(biāo)，來(lái)存取選手信息數(shù)據(jù)，編號(hào)為01 的選手，我們放到數(shù)組中下標(biāo)為 1 的位置；編號(hào)為 02 的選手，我們放到數(shù)組中下標(biāo)為 2 的位置。以此類(lèi)推，編號(hào)為 k 的選手放到數(shù)組中下標(biāo)為 k 的位置。

這就是典型的散列思想。其中，參賽選手的編號(hào)我們叫做鍵（key）或者關(guān)鍵字。我們用它來(lái)標(biāo)識(shí)一個(gè)選手。我們把參賽編號(hào)轉(zhuǎn)化為數(shù)組下標(biāo)的映射方法就叫作散列函數(shù)（或“Hash 函數(shù)”“哈希函數(shù)”），而散列函數(shù)計(jì)算得到的值就叫作散列值（或“Hash 值”“哈希值”）。

通過(guò)這個(gè)例子，我們可以總結(jié)出這樣的規(guī)律：散列表用的就是數(shù)組支持按照下標(biāo)隨機(jī)訪(fǎng)問(wèn)的時(shí)候，時(shí)間復(fù)雜度是 O(1) 的特性。我們通過(guò)散列函數(shù)把元素的鍵值映射為下標(biāo)，然后將數(shù)據(jù)存儲(chǔ)在數(shù)組中對(duì)應(yīng)下標(biāo)的位置。當(dāng)我們按照鍵值查詢(xún)?cè)貢r(shí)，我們用同樣的散列函數(shù)，將鍵值轉(zhuǎn)化數(shù)組下標(biāo)，從對(duì)應(yīng)的數(shù)組下標(biāo)的位置取數(shù)據(jù)。

散列函數(shù)

散列函數(shù)，顧名思義，它是一個(gè)函數(shù)。我們可以把它定義成 hash(key)，其中 key 表示元素的鍵值，hash(key) 的值表示經(jīng)過(guò)散列函數(shù)計(jì)算得到的散列值。

int hash(String key) {// 獲取后兩位字符string lastTwoChars = key.substr(length-2, length);// 將后兩位字符轉(zhuǎn)換為整數(shù)int hashValue = convert lastTwoChas to int-type;return hashValue;
}

剛剛的散列函數(shù)比較簡(jiǎn)單，也比較容易想到。但是，如果參賽選手的編號(hào)是隨機(jī)生成的 6 位數(shù)字，又或者用的是 a 到 z 之間的字符串，該如何構(gòu)造散列函數(shù)呢？我總結(jié)了三點(diǎn)散列函數(shù)設(shè)計(jì)的基本要求：

1. 散列函數(shù)計(jì)算得到的散列值是一個(gè)非負(fù)整數(shù)；
2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
   第一點(diǎn)和第二點(diǎn)理解起來(lái)比較簡(jiǎn)單，第三點(diǎn)理解起來(lái)可能會(huì)有問(wèn)題。這個(gè)要求看起來(lái)合情合理，但是在真實(shí)的情況下，要想找到一個(gè)不同的 key 對(duì)應(yīng)的散列值都不一樣的散列函數(shù)，幾乎是不可能的。即便像業(yè)界著名的MD5、SHA、CRC等哈希算法，也無(wú)法完全避免這種散列沖突。

散列沖突

再好的散列函數(shù)也無(wú)法避免散列沖突。那究竟該如何解決散列沖突問(wèn)題呢？我們常用的散列沖突解決方法有兩類(lèi)，開(kāi)放尋址法（open addressing）和鏈表法（chaining）。

1. 開(kāi)放尋址法
   開(kāi)放尋址法的核心思想是，如果出現(xiàn)了散列沖突，我們就重新探測(cè)一個(gè)空閑位置，將其插入。那如何重新探測(cè)新的位置呢？我先講一個(gè)比較簡(jiǎn)單的探測(cè)方法，線(xiàn)性探測(cè)（Linear Probing）。當(dāng)我們往散列表中插入數(shù)據(jù)時(shí)，如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列之后，存儲(chǔ)位置已經(jīng)被占用了，我們就從當(dāng)前位置開(kāi)始，依次往后查找，看是否有空閑位置，直到找到為止。
   
   從圖中可以看出，散列表的大小為 10，在元素 x 插入散列表之前，已經(jīng) 6 個(gè)元素插入到散列表中。x 經(jīng)過(guò) Hash 算法之后，被散列到位置下標(biāo)為 7 的位置，但是這個(gè)位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突。于是我們就順序地往后一個(gè)一個(gè)找，看有沒(méi)有空閑的位置，遍歷到尾部都沒(méi)有找到空閑的位置，于是我們?cè)購(gòu)谋眍^開(kāi)始找，直到找到空閑位置 2，于是將其插入到這個(gè)位置。
   我們通過(guò)散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素。如果相等，則說(shuō)明就是我們要找的元素；否則就順序往后依次查找。如果遍歷到數(shù)組中的空閑位置，還沒(méi)有找到，就說(shuō)明要查找的元素并沒(méi)有在散列表中。
   
   散列表跟數(shù)組一樣，不僅支持插入、查找操作，還支持刪除操作。對(duì)于使用線(xiàn)性探測(cè)法解決沖突的散列表，刪除操作稍微有些特別。我們不能單純地把要?jiǎng)h除的元素設(shè)置為空。我們可以將刪除的元素，特殊標(biāo)記為 deleted。當(dāng)線(xiàn)性探測(cè)查找的時(shí)候，遇到標(biāo)記為 deleted 的空間，并不是停下來(lái)，而是繼續(xù)往下探測(cè)。
   
   你可能已經(jīng)發(fā)現(xiàn)了，線(xiàn)性探測(cè)法其實(shí)存在很大問(wèn)題。當(dāng)散列表中插入的數(shù)據(jù)越來(lái)越多時(shí)，散列沖突發(fā)生的可能性就會(huì)越來(lái)越大，空閑位置會(huì)越來(lái)越少，線(xiàn)性探測(cè)的時(shí)間就會(huì)越來(lái)越久。
   對(duì)于開(kāi)放尋址沖突解決方法，除了線(xiàn)性探測(cè)方法之外，還有另外兩種比較經(jīng)典的探測(cè)方法，二次探測(cè)（Quadratic probing）和雙重散列（Double hashing）。
   所謂二次探測(cè)，跟線(xiàn)性探測(cè)很像，線(xiàn)性探測(cè)每次探測(cè)的步長(zhǎng)是 1，那它探測(cè)的下標(biāo)序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探測(cè)探測(cè)的步長(zhǎng)就變成了原來(lái)的“二次方”，也就是說(shuō)，它探測(cè)的下標(biāo)序列就是 hash(key)+0，hash(key)+12，hash(key)+22……
   所謂雙重散列，意思就是不僅要使用一個(gè)散列函數(shù)。我們使用一組散列函數(shù) hash1(key)，hash2(key)，hash3(key)……我們先用第一個(gè)散列函數(shù)，如果計(jì)算得到的存儲(chǔ)位置已經(jīng)被占用，再用第二個(gè)散列函數(shù)，依次類(lèi)推，直到找到空閑的存儲(chǔ)位置。

不管采用哪種探測(cè)方法，當(dāng)散列表中空閑位置不多的時(shí)候，散列沖突的概率就會(huì)大大提高。為了盡可能保證散列表的操作效率，一般情況下，我們會(huì)盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子（load factor）來(lái)表示空位的多少。裝載因子越大，說(shuō)明空閑位置越少，沖突越多，散列表的性能會(huì)下降。
2. 鏈表法
鏈表法是一種更加常用的散列沖突解決辦法，相比開(kāi)放尋址法，它要簡(jiǎn)單很多。我們來(lái)看這個(gè)圖，在散列表中，每個(gè)“桶（bucket）”或者“槽（slot）”會(huì)對(duì)應(yīng)一條鏈表，所有散列值相同的元素我們都放到相同槽位對(duì)應(yīng)的鏈表中。

插入的時(shí)候，我們只需要通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的散列槽位，將其插入到對(duì)應(yīng)鏈表中即可，所以插入的時(shí)間復(fù)雜度是 O(1)。當(dāng)查找、刪除一個(gè)元素時(shí)，我們同樣通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的槽，然后遍歷鏈表查找或者刪除。那查找或刪除操作的時(shí)間復(fù)雜度是多少呢？實(shí)際上，這兩個(gè)操作的時(shí)間復(fù)雜度跟鏈表的長(zhǎng)度 k 成正比，也就是 O(k)。對(duì)于散列比較均勻的散列函數(shù)來(lái)說(shuō)，理論上講，k=n/m，其中 n 表示散列中數(shù)據(jù)的個(gè)數(shù)，m 表示散列表中“槽”的個(gè)數(shù)。

解答開(kāi)篇

Word 文檔中單詞拼寫(xiě)檢查功能是如何實(shí)現(xiàn)的？
常用的英文單詞有 20 萬(wàn)個(gè)左右，假設(shè)單詞的平均長(zhǎng)度是 10 個(gè)字母，平均一個(gè)單詞占用 10 個(gè)字節(jié)的內(nèi)存空間，那 20 萬(wàn)英文單詞大約占 2MB 的存儲(chǔ)空間，就算放大 10 倍也就是 20MB。對(duì)于現(xiàn)在的計(jì)算機(jī)來(lái)說(shuō)，這個(gè)大小完全可以放在內(nèi)存里面。所以我們可以用散列表來(lái)存儲(chǔ)整個(gè)英文單詞詞典。當(dāng)用戶(hù)輸入某個(gè)英文單詞時(shí)，我們拿用戶(hù)輸入的單詞去散列表中查找。如果查到，則說(shuō)明拼寫(xiě)正確；如果沒(méi)有查到，則說(shuō)明拼寫(xiě)可能有誤，給予提示。借助散列表這種數(shù)據(jù)結(jié)構(gòu)，我們就可以輕松實(shí)現(xiàn)快速判斷是否存在拼寫(xiě)錯(cuò)誤。