建站
咨詢
售后
建站咨詢
新聞中心
大家好，我是梁唐。
隨著這篇文章，我們進(jìn)入了本書的第五章——哈希表。
哈希函數(shù)
要理解哈希表，就需要先理解哈希函數(shù)，而想要理解哈希函數(shù)，最好從它的原理入手。我們?yōu)槭裁葱枰：瘮?shù)，它的出現(xiàn)解決了一個(gè)什么實(shí)際的問題。
我們先來看一個(gè)簡單的問題——班級花名冊。某一次考試之后，老師拿到了全班所有同學(xué)的成績。一般情況下會被記錄進(jìn)一個(gè)類似花名冊的東西里。比如我們可以用一個(gè)結(jié)構(gòu)體記錄每個(gè)同學(xué)的信息，比如姓名、考試成績、性別。之后再創(chuàng)建一個(gè)結(jié)構(gòu)體數(shù)組就可以存下所有同學(xué)的信息。
但是在查詢的時(shí)候就有問題了。假設(shè)我們要查詢某個(gè)特定學(xué)生的成績，比如張三的成績，怎么辦呢？我們沒辦法知道張三對應(yīng)的數(shù)據(jù)存放在數(shù)組的什么位置。在這種情況下，我們只能遍歷整個(gè)數(shù)組，依次判斷，直到找到張三為止。這種枚舉遍歷的查找方式復(fù)雜度是。
在數(shù)據(jù)量很小的情況下，這種方法當(dāng)然沒問題，現(xiàn)實(shí)中老師都是這么干的。然而一旦數(shù)據(jù)量很大、查詢次數(shù)很多時(shí)，這樣的復(fù)雜度就沒辦法接受了。
怎么樣解決這個(gè)問題呢？
算法大佬們給出的答案就是哈希函數(shù)，所謂的哈希函數(shù)，它只做一件事情就是映射。我們使用數(shù)組來存儲所有同學(xué)的數(shù)據(jù)，最大的問題是我們不知道每條信息存儲的位置，所以只能遍歷來查詢。
假設(shè)我們可以設(shè)計(jì)出某種算法，它可以將學(xué)生的姓名映射成一個(gè)整數(shù)。名字不同，映射之后的結(jié)果也不同。那么利用這一點(diǎn)，我們是不是就可以解決這個(gè)問題了。
舉個(gè)例子，假設(shè)我們擁有了某個(gè)哈希函數(shù)，它對“張三”的哈希結(jié)果是1。那么我們就把張三的數(shù)據(jù)存放進(jìn)數(shù)組下標(biāo)1的位置。在查詢的“張三”的時(shí)候，我們再調(diào)用一次哈希函數(shù)傳入“張三”，會得到1。1就是張三數(shù)據(jù)儲存的下標(biāo)，那么我們只要訪問數(shù)組中對應(yīng)的位置就可以拿到張三的數(shù)據(jù)了。
這種將非整數(shù)類型的數(shù)據(jù)映射成整數(shù)的函數(shù)就叫做哈希函數(shù)。
哈希表
現(xiàn)在我們理解了哈希函數(shù)，那么哈希表又是什么呢？
哈希表實(shí)際上就是一個(gè)數(shù)組，也就是用來存儲哈希之后結(jié)果的數(shù)組。既然是數(shù)組，那么它的長度是固定的。但哈希函數(shù)返回的范圍往往要大得多。這個(gè)時(shí)候，我們可以采用取模的方法來將哈希函數(shù)的結(jié)果重映射到數(shù)組的長度以內(nèi)。
大家可以參考一下下面這段代碼：
struct P {...};
P data[10];
// 對數(shù)組長度取模
int id = hash("張三") % 10;
data[id];
哈希表的原理很好理解，但是真正要去使用的話就會遇到一些問題。最大的問題就是哈希沖突或者哈希碰撞的問題。
哈希沖突
哈希函數(shù)可以將我們的輸入映射成數(shù)字，我們可以保證，同樣的輸入可以得到同樣的映射結(jié)果。但是反之，不同的輸入映射之后的結(jié)果一定不同嗎？
我們可以從輸入輸出的集合去思考這個(gè)問題，理論上來說我們的輸入的可能性理論上是無窮的。那輸出呢？哈希函數(shù)的返回類型往往是int32或者是int64，不論是哪一種，它的取值范圍都是有限的。既然輸入的范圍無限而輸出的范圍有限，那么必然會存在多個(gè)不同的輸入但輸出結(jié)果相同的情況。
這種輸入不同，但哈希之后的結(jié)果相同的情況就稱為哈希沖突。
在哈希表當(dāng)中，由于我們還需要將哈希之后的結(jié)果對表的長度取模，因此就更加容易遇到?jīng)_突。所以指望運(yùn)氣好沒有遇到?jīng)_突是不現(xiàn)實(shí)的，我們必須在數(shù)據(jù)結(jié)構(gòu)當(dāng)中解決這個(gè)問題。
拉鏈法
針對這個(gè)問題，解決的方法有好幾種，但細(xì)究起來根據(jù)原理只有兩種，一種是拉鏈法，一種是探測法。
所謂探測法，即當(dāng)我們插入新的數(shù)據(jù)與已有的元素發(fā)生哈希碰撞時(shí)，會探測另外一個(gè)可行的位置來代替。根據(jù)探測的方法不同又可以分成線性探測、二次探測、雙哈希等方法。所以這些方法的本質(zhì)是一樣的，就是碰撞之后另外尋找一個(gè)空閑的位置來使用。
而拉鏈法不同，它不會另外探測其他的位置，而是會使用鏈表將所有哈希值相同的元素一起存放起來。所以完整的結(jié)構(gòu)是一個(gè)鏈表的數(shù)組，存取元素的時(shí)候都會經(jīng)過兩步操作。首先通過哈希算法算出下標(biāo)，找到對應(yīng)位置的鏈表。然后再在鏈表當(dāng)中進(jìn)行遍歷和插入的操作。
這里有一個(gè)trick，我們在修改鏈表中的元素時(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ù)組的長度是一個(gè)定值，那么隨著我們插入元素的增多，必然會導(dǎo)致鏈表的長度越來越長，也就沒辦法保持長度控制在了。
針對這個(gè)問題，通常的做法是擴(kuò)容 + rehash。比如Java中的HashMap會設(shè)置一個(gè)閾值，當(dāng)表中元素的個(gè)數(shù)超過閾值時(shí)就會觸發(fā)擴(kuò)容。擴(kuò)容時(shí)會將數(shù)組的長度增加一倍，接著把當(dāng)前所有的元素全部讀取一遍重新hash，再插入到擴(kuò)容之后的哈希表當(dāng)中。
擴(kuò)容會帶來額外的時(shí)間和空間開銷，時(shí)間開銷很好理解，所有元素全部重新插入一遍是的操作。另外，擴(kuò)容之后哈希表的長度翻倍，通常也會帶來浪費(fèi)，因?yàn)槲覀儧]法保證表中的元素是平均分配的。
二叉搜索樹
我們要存儲兩個(gè)變量之間的映射關(guān)系，除了使用哈希表之外還可以使用二叉搜索樹。
C++當(dāng)中，這兩者分別對應(yīng)unordered_map和map。這兩者的用法基本一致，不過底層的實(shí)現(xiàn)原理完全不同。前者基于哈希表，后者基于紅黑樹（二叉搜索樹）。
紅黑樹會直接將映射前后的結(jié)果打包一起作為樹中的節(jié)點(diǎn)存起來，利用鍵值的大小關(guān)系來建立二叉搜索樹。所以它會要求鍵值必須是可比較的，如果是我們自定義的類型，需要我們重載比較符，而哈希表則不存在這個(gè)限制。一棵平衡的二叉搜索樹的查找復(fù)雜度是，要比哈希表的復(fù)雜度要高，但二叉搜索樹存儲了節(jié)點(diǎn)之間的順序，我們可以按照大小順序遍歷所有結(jié)果，但哈希表則不能。
關(guān)于哈希表原理的部分就聊到這里，下一篇文章我們將會結(jié)合例題來實(shí)際體會一下map的應(yīng)用。
感謝大家的閱讀，如果喜歡的話，懇請幫忙轉(zhuǎn)發(fā)擴(kuò)散。算法學(xué)習(xí)之旅，與你同行。
網(wǎng)站欄目：哈希函數(shù)、哈希表、HashMap，二叉搜索樹簡介
標(biāo)題鏈接：http://www.5511xx.com/article/cdceioo.html
