動畫：散列表 | 文本編輯器是如何檢查英文單詞出錯的？

• 2019 年 12 月 27 日
• 筆記

寫在前邊

今天小鹿就早早起床開始正準備更新今日的文章，我熟練的敲打着鍵盤，突然出現了下面的情況：

咦？這編輯器查錯功能竟然比我手速還快，這我就不服氣了，我就開始瘋狂地搜着這個編輯器快速查錯功能是如何實現的

？

後來在網上一搜，都說用哈希表實現的，我思考着，用哈希表怎麼實現的，我對這次「案件」越來越感興趣，然後我繼續深入探索哈希表「案情」背後的秘密。

功夫不負有心人，我終於在維基百科找到了想要的答案：

伴隨着此次「案件」的存在疑點重重，我開始深深的陷入對散列表的思考…

思維導圖

1

什麼是散列表？

維基百科給我們散列表的定義對於新人來說確實有點難理解，如下：

散列表（Hash table，也叫哈希表），是根據鍵（Key）而直接訪問在內存存儲位置的數據結構。也就是說，它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。 —— 維基百科

那小鹿再來給解釋一波吧。何為散列表，散列表就像是我們超市的存儲私人物品的存儲櫃，我們存儲物品對應的柜子都會有對應的條形碼，我們可以通過掃描條形碼來打開對應的柜子。其實，這就類似於一個散列表。

2

如何實現散列表？

對於數據結構中的散列表是如何實現的呢？是不是還記得我們的兩位老朋友，數組和鏈表。我們之前再次強調，所有的數據結構基本都是由數組和鏈表演變而來，散列表也不例外。

我們通過自取櫃的例子，可以聯想到數組，數組是通過下標來訪問元素的，其實散列表就是數組的一種演變，那麼散列表是如何實現的呢？

我們將自取櫃的二維碼稱之為「鍵」，用它來作為柜子的唯一標識。然後把二維碼轉化為特定柜子的映射方法叫做「散列函數」（也可以稱為哈希函數）。通過映射打開對應的柜子，這個映射的值叫做「哈希值」

同樣，數組的下標對應的就是「鍵」，下標所映射到的元素就是「散列值」，這就是一個散列表。

3

哈希函數

上文中，我們提到將「鍵」映射為「哈希值」的函數，叫做哈希函數。那麼這個函數是如何實現的呢？

對於數組演變的散列表，我們可以知道哈希函數有這麼幾個特點：

• 哈希函數得到的哈希值是一個非負數的值；
• 如果「鍵」相同，通過哈希函數得到的哈希值一定相同。

有的小夥伴可能會問，同一個哈希值一定是同一個「鍵」嗎？這個問題問的好，你還真別說，還真有不是一個的可能，因為存在哈希衝突。

哈希衝突是避免不了的，就算我們項目中用到的 MD5 加密也無法避免這種情況，但能做的把這種情況概率降到最低。在我們降低概率的時候同時增加了其他的開支。有種像時間換空間，空間換時間思想的意思。

4

什麼是哈希衝突？

什麼是哈希衝突？舉個例子，比如我們往 5 個桶里放 6 個小球，每個桶中規定只能放一個，那剩下的一個不得不放入其中一個桶中，這就是所謂的哈希衝突。

難道沒有更好的方法解決哈希衝突嗎？有的，但是並不能完全解決，而是通過其他的開銷來降低衝突的概率。

5

哈希衝突的解決辦法

我們共有兩種解決辦法，開放尋址法和拉鏈法（又叫鏈表法）。

5.1

開發尋址法

開發尋址的法的原理就是如果我們發生了哈希衝突，也就是說通過散列函數得出的散列值相同，我們就重新探測一個位置，將數據存儲。那如何進行探測呢？

線性探測

所謂的線性探測，就是一個一個的進行探測如下圖動畫，在散列表中插入一個元素：

查找元素也是同樣的道理，如果在散列表中查找的元素和我們要查找的元素相同，則直接取出，否則通過線性探測，一個一個去查找，直到沒有查找到位置。

對於刪除元素呢？這就比較麻煩一點，因為我們刪除元素之後，再進行插入元素或者查找元素就出現位置空缺了，無法完成正常的操作了，所以我們刪除元素規定不能將元素進行真正的刪除，而是做一個標記，如果查找元素，遇到該標記則繼續查找。

二次探測

上邊我們是進行線性查找，二次探測就是每次探測都是原來的平方探測。

這兩種方式只是方式上的不同，如果散列表的空間不足時，產生的哈希衝突還是很大概率的。我們通常用一個閥值來表示散列表中剩餘空間的大小，我們稱這個閥值為裝載因子。（裝載因子 = 元素個數 / 散列表的大小）。

5.2

拉鏈法

我們除了開放尋址法外，我們還可以使用拉鏈法來解決哈希衝突，所謂的拉鏈法就是鏈表這個數據結構。

如果我們通過「鍵」得到的哈希值相同的時候，也就是衝突的時候，我們會在該散列表中對應的位置加一條鏈表，如果再衝突，我們繼續往對應的鏈表中添加元素。

如果我們查找、刪除元素的時候，得到的哈希值沒有，則在對應的單鏈表中進行查找。

6

小結

我們上邊分享了散列表的基本常識，回到我們開篇的問題上去，文本編輯器是如何檢查英文單詞出錯的呢？

牛津詞典的單詞一共 75 萬左右，如果不歸類、不分義，常用的英語單詞一共 25 萬左右。假設一個單詞平均占 10 個位元組，25 萬單詞四捨五入湊個整數大約 3 M。就算是 75 萬單詞，也就是 8 M。我們用散列表進行存儲，放到內存中。

當我們飛速的打着字時，計算機就會拿着你輸入的單詞去散列表中的查找，因為散列表就是數組的演變，查詢一個元素的時間複雜度為O(1)。如果可以查找到，則存在該單詞，就不會有報錯信息。否則，提示錯誤，出現下滑波浪線，提示用戶修改錯誤的單詞。