我們在這篇文章將要學習最有用的數(shù)據(jù)結(jié)構(gòu)之一—哈希表,哈希表的英文叫 Hash Table,也可以稱為散列表或者Hash 表。
哈希表用的是數(shù)組支持按照下標隨機訪問數(shù)據(jù)的特性,所以哈希表其實就是數(shù)組的一種擴展,由數(shù)組演化而來。可以說,如果沒有數(shù)組,就沒有散列表。
哈希表存儲的是由鍵(key)和值(value)組成的數(shù)據(jù)。例如,我們將每個人的性別作為數(shù)據(jù)進行存儲,鍵為人名,值為對應(yīng)的性別,其中 M 表示性別為男,F(xiàn) 表示性別為女。
為什么需要哈希表?
為了和哈希表進行對比,我們先將這些數(shù)據(jù)存儲在數(shù)組中。
此處準備了6個箱子(即長度為6的數(shù)組)來存儲數(shù)據(jù),假設(shè)我們需要查詢 Ally 的性別,由于不知道 Ally 的數(shù)據(jù)存儲在哪個箱子里,所以只能從頭開始查詢,這個操作便叫作線性查找。一般來說,我們可以把鍵當成數(shù)據(jù)的標識符,把值當成數(shù)據(jù)的內(nèi)容。
從 0 號箱子開始查找,發(fā)現(xiàn) 0 號箱子中存儲的鍵是 Joe 而不是 Ally,因此接著查找 1 號箱子。
哦豁,1 號箱子中的也不是 Ally,沒辦法,只能接著往下找。
有點小糟糕,2 號、3 號箱子中的也都不是 Ally。
功夫不負有心人,當我們查找到 4 號箱子的時候,發(fā)現(xiàn)其中數(shù)據(jù)的鍵為 Ally,把鍵對應(yīng)的值取出,我們就知道 Ally 的性別為女(F)。
通過上面的查找過程,我們發(fā)現(xiàn)數(shù)據(jù)量越多,線性查找耗費的時間就越長。由此可知:由于數(shù)據(jù)的查詢較為耗時,所以此處并不適合使用數(shù)組來存儲數(shù)據(jù)。
但使用哈希表便可以解決這個問題,首先準備好數(shù)組,這次我們用 5 個箱子的數(shù)組來存儲數(shù)據(jù)。
嘗試把 Joe 存進去,使用哈希函數(shù)(Hash)計算 Joe 的鍵,也就是字符串 Joe 的哈希值,比如得到的結(jié)果為4928。
將得到的哈希值除以數(shù)組的長度 5,求得其余數(shù),這樣的求余運算叫作mod運算,此處mod運算的結(jié)果為3。
因此,我們將 Joe 的數(shù)據(jù)存進數(shù)組的 3 號箱子中,重復(fù)前面的操作,將其他數(shù)據(jù)也存進數(shù)組中。
Sue 鍵的哈希值為 7291, mod 5 的結(jié)果為 1,將 Sue 的數(shù)據(jù)存進 1 號箱中。
Dan 鍵的哈希值為 1539, mod 5 的結(jié)果為 4,將 Dan 的數(shù)據(jù)存進 4 號箱中。
Nell 鍵的哈希值為 6276, mod 5 的結(jié)果為 1,本應(yīng)將其存進數(shù)組的 1 號箱中,但此時 1 號箱中已經(jīng)存儲了 Sue 的數(shù)據(jù),這種存儲位置重復(fù)了的情況便叫作沖突。
遇到這種情況,可使用鏈表在已有數(shù)據(jù)的后面繼續(xù)存儲新的數(shù)據(jù)(鏈表法)。
Ally 鍵的哈希值為 9143, mod 5 的結(jié)果為 3,本應(yīng)將其存儲在數(shù)組的 3 號箱中,但 3 號箱中已經(jīng)有了 Joe 的數(shù)據(jù),所以使用鏈表,在其后面存儲 Ally 的數(shù)據(jù)。
Bob 鍵的哈希值為 5278, mod 5 的結(jié)果為 3,本應(yīng)將其存儲在數(shù)組的 3 號箱中,但 3 號箱中已經(jīng)有了 Joe 和 Ally 的數(shù)據(jù),所以使用鏈表,在 Ally 的后面繼續(xù)存儲 Bob 的數(shù)據(jù)。
像這樣存儲完所有數(shù)據(jù),哈希表也就制作完成了。
接下來講解數(shù)據(jù)的查詢方法,假設(shè)我們要查詢 Dan 的性別。
為了知道 Dan 存儲在哪個箱子里,首先需要算出 Dan 鍵的哈希值,然后對其進行 mod 運算,最后得到的結(jié)果為 4,于是我們知道了它存儲在 4 號箱中。
查看 4 號箱可知,其中的數(shù)據(jù)的鍵與 Dan 一致,于是取出對應(yīng)的值,由此我們便知道了 Dan 的性別為男(M)。
那么,想要查詢 Ally 的性別時該怎么做呢?為了找到它的存儲位置,先要算出 Ally 鍵的哈希值,再對其進行 mod 運算,最終得到的結(jié)果為 3。
然而 3 號箱中數(shù)據(jù)的鍵是 Joe 而不是 Ally,此時便需要對 Joe 所在的鏈表進行線性查找。
于是我們找到了鍵為 Ally 的數(shù)據(jù),取出其對應(yīng)的值,便知道了 Ally 的性別為女(F)。
哈希沖突
在哈希表中,我們可以利用哈希函數(shù)快速訪問到數(shù)組中的目標數(shù)據(jù)。如果發(fā)生哈希沖突,就使用鏈表進行存儲,這樣一來,不管數(shù)據(jù)量為多少,我們都能夠靈活應(yīng)對。
如果數(shù)組的空間太小,使用哈希表的時候就容易發(fā)生沖突,線性查找的使用頻率也會更高;反過來,如果數(shù)組的空間太大,就會出現(xiàn)很多空箱子,造成內(nèi)存的浪費。因此,給數(shù)組設(shè)定合適的空間非常重要。
在存儲數(shù)據(jù)的過程中,如果發(fā)生沖突,可以利用鏈表在已有數(shù)據(jù)的后面插入新數(shù)據(jù)來解決沖突,這種方法被稱為鏈表法,也被稱為鏈地址法。
其中在 Java 集合類的 HashMap 中解決沖突的方法就是采用的鏈表法,建議閱讀 HashMap 源碼。
除了鏈地址法以外,還有幾種解決沖突的方法。其中,應(yīng)用較為廣泛的是開放地址法,或稱為開放尋址法。這種方法是指當沖突發(fā)生時,立刻計算出一個候補地址(數(shù)組上的位置)并將數(shù)據(jù)存進去。如果仍然有沖突,便繼續(xù)計算下一個候補地址,直到有空地址為止,可以通過多次使用哈希函數(shù)或線性探測法等方法計算候補地址。
在 Java 中,ThreadLocal所使用的就是開放地址法。
哈希函數(shù)設(shè)計的好壞決定了哈希沖突的概率,也就決定哈希表的性能。
總結(jié)
這篇文章主要講了一些比較基礎(chǔ)的哈希表知識,包括哈希表的由來、哈希沖突的解決方法。
哈希表也叫散列表,來源于數(shù)組,它借助哈希函數(shù)對數(shù)組這種數(shù)據(jù)結(jié)構(gòu)進行擴展,利用的是數(shù)組支持按照下標隨機訪問元素的特性,是存儲 Key-Value 映射的集合。
哈希表兩個核心問題是哈希函數(shù)設(shè)計和哈希沖突解決。對于某一個 Key,哈希表可以在接近 O(1) 的時間內(nèi)進行讀寫操作。哈希表通過哈希函數(shù)實現(xiàn) Key 和數(shù)組下標的轉(zhuǎn)換,通過開放尋址法和鏈表法來解決哈希沖突。哈希函數(shù)設(shè)計的好壞決定了哈希沖突的概率,也就決定哈希表的性能。
有興趣的可以在 JDK 中閱讀 HashMap 的源碼,在 JDK 8 和之前的版本的實現(xiàn)還有許多不多,比如在 JDK 8 中,引入紅黑樹,當鏈表長度太長(默認超過 8)時,鏈表就轉(zhuǎn)換為紅黑樹,就可以利用紅黑樹快速增刪改查的特點,提高 HashMap 的性能。
-
數(shù)據(jù)存儲
+關(guān)注
關(guān)注
5文章
970瀏覽量
50895 -
函數(shù)
+關(guān)注
關(guān)注
3文章
4328瀏覽量
62575 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
573瀏覽量
40124
發(fā)布評論請先 登錄
相關(guān)推薦
評論