Word文檔編輯器大家應該經常使用吧，大家有沒有留意到它編輯功能，當我們輸入一個錯誤的單詞時，單詞單面就會标紅提示“拼寫錯誤”，這個功能是怎麼實現的呢？其實啊，它是通過散列表實現的，學習了散列表原理後你就懂得這個功能的實現方式了。

散列表的英文名叫Hash Table，一般叫散列表或哈希表，散列表用的是數組支持按照下标随機訪問數據的特性，所以散列表就是數組的一種擴展，由數組演化而來，可以說，如果沒有數組就沒有散列表。

我用一個列子解釋一下，我們去遊泳館遊泳時一般都會寄存衣物，這時前台就會登記我們名字後分配一個儲物櫃編号卡，後面我們通過這個編号卡就能快速地找到櫃子存儲衣物，回去時也能快速找到櫃子取回衣物。

這裡儲物櫃是按照編号順序排列，就相當于一個數組，由于每天去遊泳的人都各不相同，就不能每個櫃子都貼上對應人的名字了，所以儲物前就會先去前台分配一個編号，再根據編号的下标存儲在數組的下标位置。

這就是典型的散列思想。每個去遊泳的人的名字我們叫做鍵(key)或者關鍵字。我們把前台通過名字分配儲物櫃号的對應過程叫作散列函數，而通過散列函數計算得到的儲物櫃号碼叫作散列值。

散列函數

散列函數，顧名思義，它就是一個函數，我們可以把它定義為hash(key)，其中key就是元素的鍵，hash(key)就是通過散列函數計算得到的散列值。

剛剛舉的例子中，散列函數其實就是前台工作人員将名字和号碼牌對應起來的一個對應關系，這個例子比較不恰當，并沒有一個固定的公式。那麼，實用場景中，要怎麼設計構造散列函數呢，我總結了三點基本的要求：

1. 散列函數計算得到的散列值必須是一個非負整數；
2. key1=key2，那hash(key1)=hash(key2);
3. key1≠key2，那hash(key1)≠hash(key2);

第一點很容易理解，散列值最後是作為數組的下标的，數組下标是從0開始的；第二點，相同的key，得到的散列值也應該是相同的。

第三點看起來合情合理，但是在真實場景中，要想找到一個不同的鍵得出的散列值都不一樣的散列函數幾乎是不可能的，即便像業界著名的MD5、SHA、CRC等哈希算法也無法避免散列沖突，因為數組的空間有限，函數計算得到的值還必須在數組個數範圍内，因此就會有很大概率出現沖突。

再好的散列函數也無法避免散列沖突，那怎麼辦呢？隻能通過其他方式解決，一般散列沖突的解決辦法有兩類：開放尋址法和鍊表法。

1.開放尋址法

開放尋址法的核心思想是，如果出現了散列沖突，就尋找下一個空閑位置，插入新的數據。開放尋址法也有多種方式，将介紹一個簡單的探測方法，線性探測(Linear Probing)。

線性探測

當我們往散列表插入數據時，如果經過散列函數散列之後，存儲位置已經被占用了，我們就從當前位置依次往後查找，将數據插入到找到的空閑位置，如果遍曆到尾部仍沒有空閑位置，我們就從表頭開始找，直到找到為止。如圖所示

通過線性探測要查找數據時，和插入數據類似，也是通過散列函數得到對應位置的元素，和要查詢的數據作對比，如果一緻，則取出該值，如果不一緻，則從該位置往下到散列表的空閑位置一個個查找，如果找到，取出對應值，如果沒有找到，則數據不存在。

而但通過線性探測法删除一個元素時就比較麻煩，如果查找到對應的元素時直接将該元素對應的位置置空的話，那按照上面說的線性探測查找方法，遇到一個空的位置時就停止查詢，那這個空位置如果是剛剛被删除的元素，這時候這個查找方法就失敗了。所以，删除一個元素時并不是直接删除，而是在要删除的位置标記deleted。在查找一個元素時如果遇到deleted标記的元素，則繼續往下查找，如下圖所示。

通過上面的介紹，我們可以知道，線性探測法有一個弊端。就是散列表剩餘空間不足時，就會頻繁地出現散列沖突，導緻效率不高，極端情況下插入一個元素會時間複雜度為O(n)。

對于開放尋址的沖突解決方法，除了線性探測方法外，還有另外兩種比較經典的探測方法，分别為二次探測和雙重散列。

二次探測

二次探測法，和線性探測法類似，線性探測每次的探測步長是1步，它探測的下标序列是hash(key) 0，hash(key) 1，hash(key) 2，hash(key) 3...而二次探測的步長是原來的“二次方步長”，它的探測下标序列是列是hash(key) 0，hash(key) 1，hash(key) 4，hash(key) 9...

雙重散列

雙重散列，意思是不僅要使用一個散列函數，我們要使用一組散列函數hash1(key)，hash2(key)，hash3(key)...先使用第一個散列函數計算散列位置，如果出現沖突，再使用第二個散列函數，依次類推，直到找到空閑位置。

不管使用哪種線性沖突解決方法，當空閑位置較少的時候，出現沖突的概率就會加大，為了保證散列表的操作效率，一般會保證散列表有一定比例的空閑位置，我們用裝載因子來表示散列表的空閑比例，它的計算公式如下

散列表的裝載因子 = 填入表中的元素個數 / 散列表長度

2.鍊表法

鍊表法是一種更加普遍的散列表沖突解決方法，相比線性探測法，它更簡單更容易理解。如圖所示，散列表的元素就是一個“桶”或“槽”，每個桶都放入一個鍊表，将散列值相同的元素都放在同一個鍊表中。

當插入的時候，我們隻需要通過散列函數計算出對應的散列槽位，将其插入到對應的鍊表中即可，時間複雜度為O(1)。當要查詢或删除時，即通過同樣的方法找到對應的槽位，再遍曆鍊表查詢或删除，那查詢和删除的時間複雜度是多少呢？

查詢和删除的時間複雜度和每個槽位鍊表的長度成正比，假設鍊表平均長度為k，那時間複雜度則為O(k)。對于散列比較均勻的散列函數，理論上k = n / m，其中n為散列表中數據的個數，m為散列表的長度。

有了上面的散列表的介紹，我們再來回顧下開篇提到的Word文檔編輯器的拼寫錯誤提示是怎麼實現的？

我們常用的英文單詞大約有20萬個左右，假設平均每個單詞有10個字母，那每個單詞就大約有10個字節，20萬個單詞就有差不多2M左右的大小，對于現代的計算機來說，完全可以将20萬個單詞放在内存中，存儲在散列表，每次輸入一個單詞時，就通過散列表查找，如果能找到就是拼寫正确的，如果找不到則提示拼寫錯誤。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!