大家好，我是梁唐。

隨著這篇文章，我們進入了本書的第五章——哈希表。

哈希函數

要理解哈希表，就需要先理解哈希函數，而想要理解哈希函數，最好從它的原理入手。我們為什么需要哈希函數，它的出現解決了一個什么實際的問題。

我們先來看一個簡單的問題——班級花名冊。某一次考試之后，老師拿到了全班所有同學的成績。一般情況下會被記錄進一個類似花名冊的東西里。比如我們可以用一個結構體記錄每個同學的信息，比如姓名、考試成績、性別。之后再創建一個結構體數組就可以存下所有同學的信息。

但是在查詢的時候就有問題了。假設我們要查詢某個特定學生的成績，比如張三的成績，怎么辦呢？我們沒辦法知道張三對應的數據存放在數組的什么位置。在這種情況下，我們只能遍歷整個數組，依次判斷，直到找到張三為止。這種枚舉遍歷的查找方式復雜度是。

在數據量很小的情況下，這種方法當然沒問題，現實中老師都是這么干的。然而一旦數據量很大、查詢次數很多時，這樣的復雜度就沒辦法接受了。

怎么樣解決這個問題呢？

算法大佬們給出的答案就是哈希函數，所謂的哈希函數，它只做一件事情就是映射。我們使用數組來存儲所有同學的數據，最大的問題是我們不知道每條信息存儲的位置，所以只能遍歷來查詢。

假設我們可以設計出某種算法，它可以將學生的姓名映射成一個整數。名字不同，映射之后的結果也不同。那么利用這一點，我們是不是就可以解決這個問題了。

舉個例子，假設我們擁有了某個哈希函數，它對“張三”的哈希結果是1。那么我們就把張三的數據存放進數組下標1的位置。在查詢的“張三”的時候，我們再調用一次哈希函數傳入“張三”，會得到1。1就是張三數據儲存的下標，那么我們只要訪問數組中對應的位置就可以拿到張三的數據了。

這種將非整數類型的數據映射成整數的函數就叫做哈希函數。

哈希表

現在我們理解了哈希函數，那么哈希表又是什么呢？

哈希表實際上就是一個數組，也就是用來存儲哈希之后結果的數組。既然是數組，那么它的長度是固定的。但哈希函數返回的范圍往往要大得多。這個時候，我們可以采用取模的方法來將哈希函數的結果重映射到數組的長度以內。

大家可以參考一下下面這段代碼：

struct P {...};
P data[10];
// 對數組長度取模
int id = hash("張三") % 10;
data[id];

哈希表的原理很好理解，但是真正要去使用的話就會遇到一些問題。最大的問題就是哈希沖突或者哈希碰撞的問題。

哈希沖突

哈希函數可以將我們的輸入映射成數字，我們可以保證，同樣的輸入可以得到同樣的映射結果。但是反之，不同的輸入映射之后的結果一定不同嗎？

我們可以從輸入輸出的集合去思考這個問題，理論上來說我們的輸入的可能性理論上是無窮的。那輸出呢？哈希函數的返回類型往往是int32或者是int64，不論是哪一種，它的取值范圍都是有限的。既然輸入的范圍無限而輸出的范圍有限，那么必然會存在多個不同的輸入但輸出結果相同的情況。

這種輸入不同，但哈希之后的結果相同的情況就稱為哈希沖突。

在哈希表當中，由于我們還需要將哈希之后的結果對表的長度取模，因此就更加容易遇到沖突。所以指望運氣好沒有遇到沖突是不現實的，我們必須在數據結構當中解決這個問題。

拉鏈法

針對這個問題，解決的方法有好幾種，但細究起來根據原理只有兩種，一種是拉鏈法，一種是探測法。

所謂探測法，即當我們插入新的數據與已有的元素發生哈希碰撞時，會探測另外一個可行的位置來代替。根據探測的方法不同又可以分成線性探測、二次探測、雙哈希等方法。所以這些方法的本質是一樣的，就是碰撞之后另外尋找一個空閑的位置來使用。

而拉鏈法不同，它不會另外探測其他的位置，而是會使用鏈表將所有哈希值相同的元素一起存放起來。所以完整的結構是一個鏈表的數組，存取元素的時候都會經過兩步操作。首先通過哈希算法算出下標，找到對應位置的鏈表。然后再在鏈表當中進行遍歷和插入的操作。

這里有一個trick，我們在修改鏈表中的元素時注意保證鏈表的有序性。這樣在搜索元素時我們就不必遍歷完整個鏈表，當遇到比要查找的元素更大的元素時，就已經說明要找的元素不存在了。

Java中的HashMap?以及C++中的unordered_map，都是基于這樣的哈希表實現的。

哈希函數可以被認為是復雜度的操作，在鏈表中的元素不太多時，那么整體的增刪改查的復雜度都可以控制在。這樣的復雜度看起來非常完美，但是這里面有一個小問題。哈希表數組的長度是一個定值，那么隨著我們插入元素的增多，必然會導致鏈表的長度越來越長，也就沒辦法保持長度控制在了。

針對這個問題，通常的做法是擴容 + rehash。比如Java中的HashMap會設置一個閾值，當表中元素的個數超過閾值時就會觸發擴容。擴容時會將數組的長度增加一倍，接著把當前所有的元素全部讀取一遍重新hash，再插入到擴容之后的哈希表當中。

擴容會帶來額外的時間和空間開銷，時間開銷很好理解，所有元素全部重新插入一遍是的操作。另外，擴容之后哈希表的長度翻倍，通常也會帶來浪費，因為我們沒法保證表中的元素是平均分配的。

二叉搜索樹

我們要存儲兩個變量之間的映射關系，除了使用哈希表之外還可以使用二叉搜索樹。

C++當中，這兩者分別對應unordered_map和map。這兩者的用法基本一致，不過底層的實現原理完全不同。前者基于哈希表，后者基于紅黑樹（二叉搜索樹）。

紅黑樹會直接將映射前后的結果打包一起作為樹中的節點存起來，利用鍵值的大小關系來建立二叉搜索樹。所以它會要求鍵值必須是可比較的，如果是我們自定義的類型，需要我們重載比較符，而哈希表則不存在這個限制。一棵平衡的二叉搜索樹的查找復雜度是，要比哈希表的復雜度要高，但二叉搜索樹存儲了節點之間的順序，我們可以按照大小順序遍歷所有結果，但哈希表則不能。

關于哈希表原理的部分就聊到這里，下一篇文章我們將會結合例題來實際體會一下map的應用。

感謝大家的閱讀，如果喜歡的話，懇請幫忙轉發擴散。算法學習之旅，與你同行。