大家好，我是梁唐。

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

哈希函數(shù)

要理解哈希表，就需要先理解哈希函數(shù)，而想要理解哈希函數(shù)，最好從它的原理入手。我們?yōu)槭裁葱枰：瘮?shù)，它的出現(xiàn)解決了一個(gè)什么實(shí)際的問題。

我們先來看一個(gè)簡(jiǎn)單的問題——班級(jí)花名冊(cè)。某一次考試之后，老師拿到了全班所有同學(xué)的成績(jī)。一般情況下會(huì)被記錄進(jìn)一個(gè)類似花名冊(cè)的東西里。比如我們可以用一個(gè)結(jié)構(gòu)體記錄每個(gè)同學(xué)的信息，比如姓名、考試成績(jī)、性別。之后再創(chuàng)建一個(gè)結(jié)構(gòu)體數(shù)組就可以存下所有同學(xué)的信息。

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

在數(shù)據(jù)量很小的情況下，這種方法當(dāng)然沒問題，現(xiàn)實(shí)中老師都是這么干的。然而一旦數(shù)據(jù)量很大、查詢次數(shù)很多時(shí)，這樣的復(fù)雜度就沒辦法接受了。

怎么樣解決這個(gè)問題呢？

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

假設(shè)我們可以設(shè)計(jì)出某種算法，它可以將學(xué)生的姓名映射成一個(gè)整數(shù)。名字不同，映射之后的結(jié)果也不同。那么利用這一點(diǎn)，我們是不是就可以解決這個(gè)問題了。

舉個(gè)例子，假設(shè)我們擁有了某個(gè)哈希函數(shù)，它對(duì)“張三”的哈希結(jié)果是1。那么我們就把張三的數(shù)據(jù)存放進(jìn)數(shù)組下標(biāo)1的位置。在查詢的“張三”的時(shí)候，我們?cè)僬{(diào)用一次哈希函數(shù)傳入“張三”，會(huì)得到1。1就是張三數(shù)據(jù)儲(chǔ)存的下標(biāo)，那么我們只要訪問數(shù)組中對(duì)應(yīng)的位置就可以拿到張三的數(shù)據(jù)了。

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

哈希表

現(xiàn)在我們理解了哈希函數(shù)，那么哈希表又是什么呢？

哈希表實(shí)際上就是一個(gè)數(shù)組，也就是用來存儲(chǔ)哈希之后結(jié)果的數(shù)組。既然是數(shù)組，那么它的長(zhǎng)度是固定的。但哈希函數(shù)返回的范圍往往要大得多。這個(gè)時(shí)候，我們可以采用取模的方法來將哈希函數(shù)的結(jié)果重映射到數(shù)組的長(zhǎng)度以內(nèi)。

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

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

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

哈希沖突

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

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

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

在哈希表當(dāng)中，由于我們還需要將哈希之后的結(jié)果對(duì)表的長(zhǎng)度取模，因此就更加容易遇到?jīng)_突。所以指望運(yùn)氣好沒有遇到?jīng)_突是不現(xiàn)實(shí)的，我們必須在數(shù)據(jù)結(jié)構(gòu)當(dāng)中解決這個(gè)問題。

拉鏈法

針對(duì)這個(gè)問題，解決的方法有好幾種，但細(xì)究起來根據(jù)原理只有兩種，一種是拉鏈法，一種是探測(cè)法。

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

而拉鏈法不同，它不會(huì)另外探測(cè)其他的位置，而是會(huì)使用鏈表將所有哈希值相同的元素一起存放起來。所以完整的結(jié)構(gòu)是一個(gè)鏈表的數(shù)組，存取元素的時(shí)候都會(huì)經(jīng)過兩步操作。首先通過哈希算法算出下標(biāo)，找到對(duì)應(yīng)位置的鏈表。然后再在鏈表當(dāng)中進(jìn)行遍歷和插入的操作。

這里有一個(gè)trick，我們?cè)谛薷逆湵碇械脑貢r(shí)注意保證鏈表的有序性。這樣在搜索元素時(shí)我們就不必遍歷完整個(gè)鏈表，當(dāng)遇到比要查找的元素更大的元素時(shí)，就已經(jīng)說明要找的元素不存在了。

Java中的HashMap?以及C++中的unordered_map，都是基于這樣的哈希表實(shí)現(xiàn)的。

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

針對(duì)這個(gè)問題，通常的做法是擴(kuò)容 + rehash。比如Java中的HashMap會(huì)設(shè)置一個(gè)閾值，當(dāng)表中元素的個(gè)數(shù)超過閾值時(shí)就會(huì)觸發(fā)擴(kuò)容。擴(kuò)容時(shí)會(huì)將數(shù)組的長(zhǎng)度增加一倍，接著把當(dāng)前所有的元素全部讀取一遍重新hash，再插入到擴(kuò)容之后的哈希表當(dāng)中。

擴(kuò)容會(huì)帶來額外的時(shí)間和空間開銷，時(shí)間開銷很好理解，所有元素全部重新插入一遍是的操作。另外，擴(kuò)容之后哈希表的長(zhǎng)度翻倍，通常也會(huì)帶來浪費(fèi)，因?yàn)槲覀儧]法保證表中的元素是平均分配的。

二叉搜索樹

我們要存儲(chǔ)兩個(gè)變量之間的映射關(guān)系，除了使用哈希表之外還可以使用二叉搜索樹。

C++當(dāng)中，這兩者分別對(duì)應(yīng)unordered_map和map。這兩者的用法基本一致，不過底層的實(shí)現(xiàn)原理完全不同。前者基于哈希表，后者基于紅黑樹（二叉搜索樹）。

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

關(guān)于哈希表原理的部分就聊到這里，下一篇文章我們將會(huì)結(jié)合例題來實(shí)際體會(huì)一下map的應(yīng)用。

感謝大家的閱讀，如果喜歡的話，懇請(qǐng)幫忙轉(zhuǎn)發(fā)擴(kuò)散。算法學(xué)習(xí)之旅，與你同行。