1. 哈希表簡介

哈希表（Hash Table）：也叫做散列表。是根據(jù)關(guān)鍵碼值（Key Value）直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。

哈希表通過「鍵 key 」和「映射函數(shù) Hash(key) 」計算出對應(yīng)的「值 value」，把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做「哈希函數(shù)（散列函數(shù)）」，存放記錄的數(shù)組叫做「哈希表（散列表）」。

哈希表的關(guān)鍵思想是使用哈希函數(shù)，將鍵 key 映射到對應(yīng)表的某個區(qū)塊中。我們可以將算法思想分為兩個部分：

• 向哈希表中插入一個關(guān)鍵碼值：哈希函數(shù)決定該關(guān)鍵字的對應(yīng)值應(yīng)該存放到表中的哪個區(qū)塊，并將對應(yīng)值存放到該區(qū)塊中。

• 在哈希表中搜索一個關(guān)鍵碼值：使用相同的哈希函數(shù)從哈希表中查找對應(yīng)的區(qū)塊，并在特定的區(qū)塊搜索該關(guān)鍵字對應(yīng)的值。

哈希表的原理示例圖如下所示：

在上圖例子中，我們使用 value = Hash(key) = key // 1000 作為哈希函數(shù)。// 符號代表整除。我們以這個例子來說明一下哈希表的插入和查找策略。

• 向哈希表中插入一個關(guān)鍵碼值：通過哈希函數(shù)解析關(guān)鍵字，并將對應(yīng)值存放到該區(qū)塊中。

  • 比如：0138 通過哈希函數(shù) Hash(key) = 0138 // 100 = 0，得出應(yīng)將 0138 分配到0 所在的區(qū)塊中。

• 在哈希表中搜索一個關(guān)鍵碼值：通過哈希函數(shù)解析關(guān)鍵字，并在特定的區(qū)塊搜索該關(guān)鍵字對應(yīng)的值。

  • 比如：查找 2321，通過哈希函數(shù)，得出 2321 應(yīng)該在 2 所對應(yīng)的區(qū)塊中。然后我們從 2 對應(yīng)的區(qū)塊中繼續(xù)搜索，并在 2 對應(yīng)的區(qū)塊中成功找到了 2321。

  • 比如：查找 3214，通過哈希函數(shù)，得出 3214 應(yīng)該在 3 所對應(yīng)的區(qū)塊中。然后我們從 3 對應(yīng)的區(qū)塊中繼續(xù)搜索，但并沒有找到對應(yīng)值，則說明 3214 不在哈希表中。

哈希表在生活中的應(yīng)用也很廣泛，其中一個常見例子就是「查字典」。

比如為了查找 贊 這個字的具體意思，我們在字典中根據(jù)這個字的拼音索引 zan，查找到對應(yīng)的頁碼為 599。然后我們就可以翻到字典的第 599 頁查看 贊 字相關(guān)的解釋了。

在這個例子中：

• 存放所有拼音和對應(yīng)地址的表可以看做是 「哈希表」。

• 贊 字的拼音索引 zan 可以看做是哈希表中的 「關(guān)鍵字 key」。

• 根據(jù)拼音索引 zan 來確定字對應(yīng)頁碼的過程可以看做是哈希表中的 「哈希函數(shù) Hash(key)」。

• 查找到的對應(yīng)頁碼 599 可以看做是哈希表中的 「哈希地址 value」。

2. 哈希函數(shù)

哈希函數(shù)（Hash Function）：將哈希表中元素的關(guān)鍵鍵值映射為元素存儲位置的函數(shù)。

哈希函數(shù)是哈希表中最重要的部分。一般來說，哈希函數(shù)會滿足以下幾個條件：

• 哈希函數(shù)應(yīng)該易于計算，并且盡量使計算出來的索引值均勻分布。

• 哈希函數(shù)計算得到的哈希值是一個固定長度的輸出值。

• 如果 Hash(key1) 不等于 Hash(key2)，那么 key1、key2 一定不相等。

• 如果 Hash(key1) 等于 Hash(key2)，那么 key1、key2 可能相等，也可能不相等（會發(fā)生哈希碰撞）。

在哈希表的實際應(yīng)用中，關(guān)鍵字的類型除了數(shù)字類，還有可能是字符串類型、浮點數(shù)類型、大整數(shù)類型，甚至還有可能是幾種類型的組合。一般我們會將各種類型的關(guān)鍵字先轉(zhuǎn)換為整數(shù)類型，再通過哈希函數(shù)，將其映射到哈希表中。

而關(guān)于整數(shù)類型的關(guān)鍵字，通常用到的哈希函數(shù)方法有：直接定址法、除留余數(shù)法、平方取中法、基數(shù)轉(zhuǎn)換法、數(shù)字分析法、折疊法、隨機數(shù)法、乘積法、點積法等。下面我們介紹幾個常用的哈希函數(shù)方法。

2.1 直接定址法

• 直接定址法：取關(guān)鍵字本身 / 關(guān)鍵字的某個線性函數(shù)值 作為哈希地址。即：Hash(key) = key 或者 Hash(key) = a * key + b，其中 a 和 b 為常數(shù)。

這種方法計算最簡單，且不會產(chǎn)生沖突。適合于關(guān)鍵字分布基本連續(xù)的情況，如果關(guān)鍵字分布不連續(xù)，空位較多，則會造成存儲空間的浪費。

舉一個例子，假設(shè)我們有一個記錄了從 1 歲到 100 歲的人口數(shù)字統(tǒng)計表。其中年齡為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身，如下表所示。

比如我們想要查詢 25 歲的人有多少，則只要查詢表中第 25 項即可。

2.2 除留余數(shù)法

• 除留余數(shù)法：假設(shè)哈希表的表長為 m，取一個不大于 m 但接近或等于 m 的質(zhì)數(shù) p，利用取模運算，將關(guān)鍵字轉(zhuǎn)換為哈希地址。即：Hash(key) = key % p，其中 p 為不大于 m 的質(zhì)數(shù)。

這也是一種簡單且常用的哈希函數(shù)方法。其關(guān)鍵點在于 p 的選擇。根據(jù)經(jīng)驗而言，一般 p 取素數(shù)或者 m，這樣可以盡可能的減少沖突。

比如我們需要將 7 個數(shù) [432, 5, 128, 193, 92, 111, 88] 存儲在 11 個區(qū)塊中（長度為 11 的數(shù)組），通過除留余數(shù)法將這 7 個數(shù)應(yīng)分別位于如下地址：

2.3 平方取中法

• 平方取中法：先通過求關(guān)鍵字平方值的方式擴大相近數(shù)之間的差別，然后根據(jù)表長度取關(guān)鍵字平方值的中間幾位數(shù)為哈希地址。

  • 比如：Hash(key) = (key * key) // 100 % 1000，先計算平方，去除末尾的 2 位數(shù)，再取中間 3 位數(shù)作為哈希地址。

這種方法因為關(guān)鍵字平方值的中間幾位數(shù)和原關(guān)鍵字的每一位數(shù)都相關(guān)，所以產(chǎn)生的哈希地址也比較均勻，有利于減少沖突的發(fā)生。

2.4 基數(shù)轉(zhuǎn)換法

• 基數(shù)轉(zhuǎn)換法：將關(guān)鍵字看成另一種進制的數(shù)再轉(zhuǎn)換成原來進制的數(shù)，然后選其中幾位作為哈希地址。

  • 比如，將關(guān)鍵字看做是 13 進制的數(shù)，再將其轉(zhuǎn)變?yōu)?10 進制的數(shù)，將其作為哈希地址。

以 343246 為例，哈希地址計算方式如下：

$343246{13} = 3 \times 13^5 + 4 \times 13^4 + 3 \times 13^3 + 2 \times 13^2 + 4 \times 13^1 + 6 \times 13^0 = 1235110{10}$

3. 哈希沖突

哈希沖突（Hash Collision）：不同的關(guān)鍵字通過同一個哈希函數(shù)可能得到同一哈希地址，即 key1 ≠ key2，而 Hash(key1) = Hash(key2)，這種現(xiàn)象稱為哈希沖突。

理想狀態(tài)下，我們的哈希函數(shù)是完美的一對一映射，即一個關(guān)鍵字（key）對應(yīng)一個值（value），不需要處理沖突。但是一般情況下，不同的關(guān)鍵字 key 可能對應(yīng)了同一個值 value，這就發(fā)生了哈希沖突。

設(shè)計再好的哈希函數(shù)也無法完全避免哈希沖突。所以就需要通過一定的方法來解決哈希沖突問題。常用的哈希沖突解決方法主要是兩類：「開放地址法（Open Addressing）」 和 「鏈地址法（Chaining）」。

3.1 開放地址法

開放地址法（Open Addressing）：指的是將哈希表中的「空地址」向處理沖突開放。當(dāng)哈希表未滿時，處理沖突時需要嘗試另外的單元，直到找到空的單元為止。

當(dāng)發(fā)生沖突時，開放地址法按照下面的方法求得后繼哈希地址：H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, ..., n (n ≤ m - 1)。

• H(i) 是在處理沖突中得到的地址序列。即在第 1 次沖突（i = 1）時經(jīng)過處理得到一個新地址 H(1)，如果在 H(1) 處仍然發(fā)生沖突（i = 2）時經(jīng)過處理時得到另一個新地址 H(2) …… 如此下去，直到求得的 H(n) 不再發(fā)生沖突。

• Hash(key) 是哈希函數(shù)，m 是哈希表表長，對哈希表長取余的目的是為了使得到的下一個地址一定落在哈希表中。

• F(i) 是沖突解決方法，取法可以有以下幾種：

  • 線性探測法：$F(i) = 1, 2, 3, ..., m - 1$。

  • 二次探測法：$F(i) = 1^2, -1^2, 2^2, -2^2, ..., \pm n^2(n \le m / 2)$。

  • 偽隨機數(shù)序列：$F(i) = 偽隨機數(shù)序列$。

舉個例子說說明一下如何用以上三種沖突解決方法處理沖突，并得到新地址 H(i)。例如，在長度為 11 的哈希表中已經(jīng)填有關(guān)鍵字分別為 28、49、18 的記錄（哈希函數(shù)為 Hash(key) = key % 11）?，F(xiàn)在將插入關(guān)鍵字為 38 的新紀錄。根據(jù)哈希函數(shù)得到的哈希地址為 5，產(chǎn)生沖突。接下來分別使用這三種沖突解決方法處理沖突。

• 使用線性探測法：得到下一個地址 H(1) = (5 + 1) % 11 = 6，仍然沖突；繼續(xù)求出 H(2) = (5 + 2) % 11 = 7，仍然沖突；繼續(xù)求出 H(3) = (5 + 3) % 11 = 8，8 對應(yīng)的地址為空，處理沖突過程結(jié)束，記錄填入哈希表中序號為 8 的位置。

• 使用二次探測法：得到下一個地址 H(1) = (5 + 1*1) % 11 = 6，仍然沖突；繼續(xù)求出 H(2) = (5 - 1*1) % 11 = 4，4 對應(yīng)的地址為空，處理沖突過程結(jié)束，記錄填入哈希表中序號為 4 的位置。

• 使用偽隨機數(shù)序列：假設(shè)偽隨機數(shù)為 9，則得到下一個地址 H(1) = (9 + 5) % 11 = 3，3 對應(yīng)的地址為空，處理沖突過程結(jié)束，記錄填入哈希表中序號為 3 的位置。

使用這三種方法處理沖突的結(jié)果如下圖所示：

3.2 鏈地址法

鏈地址法（Chaining）：將具有相同哈希地址的元素（或記錄）存儲在同一個線性鏈表中。

鏈地址法是一種更加常用的哈希沖突解決方法。相比于開放地址法，鏈地址法更加簡單。

我們假設(shè)哈希函數(shù)產(chǎn)生的哈希地址區(qū)間為 [0, m - 1]，哈希表的表長為 m。則可以將哈希表定義為一個有 m 個頭節(jié)點組成的鏈表指針數(shù)組 T。

• 這樣在插入關(guān)鍵字的時候，我們只需要通過哈希函數(shù) Hash(key) 計算出對應(yīng)的哈希地址 i，然后將其以鏈表節(jié)點的形式插入到以 T[i] 為頭節(jié)點的單鏈表中。在鏈表中插入位置可以在表頭或表尾，也可以在中間。如果每次插入位置為表頭，則插入操作的時間復(fù)雜度為 $O(1)$。

• 而在在查詢關(guān)鍵字的時候，我們只需要通過哈希函數(shù) Hash(key) 計算出對應(yīng)的哈希地址 i，然后將對應(yīng)位置上的鏈表整個掃描一遍，比較鏈表中每個鏈節(jié)點的鍵值與查詢的鍵值是否一致。查詢操作的時間復(fù)雜度跟鏈表的長度 k 成正比，也就是 $O(k)$。對于哈希地址比較均勻的哈希函數(shù)來說，理論上講，k = n // m，其中 n 為關(guān)鍵字的個數(shù)，m 為哈希表的表長。

舉個例子來說明如何使用鏈地址法處理沖突。假設(shè)現(xiàn)在要存入的關(guān)鍵字集合 keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32]。再假定哈希函數(shù)為 Hash(key) = key % 13，哈希表的表長 m = 13，哈希地址范圍為 [0, m - 1]。將這些關(guān)鍵字使用鏈地址法處理沖突，并按順序加入哈希表中（圖示為插入鏈表表尾位置），最終得到的哈希表如下圖所示。

相對于開放地址法，采用鏈地址法處理沖突要多占用一些存儲空間（主要是鏈節(jié)點占用空間）。但它可以減少在進行插入和查找具有相同哈希地址的關(guān)鍵字的操作過程中的平均查找長度。這是因為在鏈地址法中，待比較的關(guān)鍵字都是具有相同哈希地址的元素，而在開放地址法中，待比較的關(guān)鍵字不僅包含具有相同哈希地址的元素，而且還包含哈希地址不相同的元素。

4. 哈希表總結(jié)

本文講解了一些比較基礎(chǔ)、偏理論的哈希表知識。包含哈希表的定義，哈希函數(shù)、哈希沖突以及哈希沖突的解決方法。

• 哈希表（Hash Table）：通過鍵 key 和一個映射函數(shù) Hash(key) 計算出對應(yīng)的值 value，把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。

• 哈希函數(shù)（Hash Function）：將哈希表中元素的關(guān)鍵鍵值映射為元素存儲位置的函數(shù)。

• 哈希沖突（Hash Collision）：不同的關(guān)鍵字通過同一個哈希函數(shù)可能得到同一哈希地址。

哈希表的兩個核心問題是：「哈希函數(shù)的構(gòu)建」 和 「哈希沖突的解決方法」。

• 常用的哈希函數(shù)方法有：直接定址法、除留余數(shù)法、平方取中法、基數(shù)轉(zhuǎn)換法、數(shù)字分析法、折疊法、隨機數(shù)法、乘積法、點積法等。

• 常用的哈希沖突的解決方法有兩種：開放地址法和鏈地址法。文章來源地址http://www.zghlxwxcb.cn/news/detail-648024.html

到了這里，關(guān)于算法數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)——哈希表（Hash Table）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！