前言

       今天來分享一道比較好的面試題，“HashMap 是怎么解決哈希沖突的？”對于這個問題，我們一起看看考察點(diǎn)和比較好的回答吧！

考察點(diǎn)

      現(xiàn)在的企業(yè)級開發(fā)中HashMap幾乎是最常用到的容器，了解HashMap 是怎么解決哈希沖突的，有助于我們開發(fā)出更加優(yōu)秀的代碼。那么這個問題就是面試官想考察我們是不是平日里善于積累，仔細(xì)思考這方面的知識！

回答  

關(guān)于這個問題，我從三個方面來回答：

1.hash沖突的基礎(chǔ)就是hash算法和hash表這種數(shù)據(jù)結(jié)構(gòu)。先講講hash算法和hash表。

①Hash 算法，就是通過散列算法，把任意長度的輸入變成固定長度的輸出。這個輸出就是散列值。

hashValue1  = hash(inputStr1);
hashValue2  = hash(inputStr2);
hashValue1和hashValue2的長度一樣

②Hash 表又叫做“散列表”，其本質(zhì)是通過key，可以直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。因此在表現(xiàn)上，我們可以通過hash函數(shù)把key映射到散列表中的某個位置，進(jìn)而獲取這個位置的數(shù)據(jù)，這樣能夠加快查找速度。

③那么我們所說的hash 沖突，因為哈希算法計算的數(shù)據(jù)是無窮的，而計算的結(jié)果范圍是有限的，這樣就會造成不同的輸入得到的結(jié)果確實一樣的情況。也就是說發(fā)生了沖突。如圖所示：

2.如何結(jié)果hash沖突呢？這里講一下常用的4中方法。

①開放定址法，也被稱為線性探測法，其原理是這樣的，從發(fā)生沖突的那個位置開始，通過一定的次序從hash表里面找一個空閑的位置。之后將發(fā)生沖突的元素存入到這個空閑位置中。在應(yīng)用上面，我們常見的ThreadLocal就是用到了線性探測法來解決hash沖突。如圖，在 hash 表索引 1 的位置存了一個 key=name，當(dāng)再次添加key=hobby 時hash 計算得到的索引也是 1，這個就是 hash 沖突。而開放定址法，就是按順序向前找到一個空閑的位置來存儲沖突的 key。

②鏈?zhǔn)綄ぶ贩ǎ@是一種非常常見的方法，簡單理解就是把存在 hash 沖突的 key，以單向鏈表的方式來存儲，比如 HashMap 就是采用鏈?zhǔn)綄ぶ贩▉韺崿F(xiàn)的。向這樣一種情況（如圖），存在沖突的 key 直接以單向鏈表的方式進(jìn)行存儲。

③再 hash 法，就是當(dāng)通過某個 hash 函數(shù)計算的 key 存在沖突時，再用另外一個 hash 函數(shù)對這個 key 做 hash，一直運(yùn)算直到不再產(chǎn)生沖突。這種方式會增加計算時間，性能影響較大。

④. 建立公共溢出區(qū)， 就是把 hash 表分為基本表和溢出表兩個部分，凡是存在沖突的元素，一律放入到溢出表中。

3.HashMap 在 JDK1.8 版本中，通過鏈?zhǔn)綄ぶ贩?紅黑樹的方式來解決 hash 沖突問題，其中紅黑樹是為了優(yōu)化 Hash 表鏈表過長導(dǎo)致時間復(fù)雜度增加的問題。當(dāng)鏈表長度大于 8 并且 hash 表的容量大于 64 的時候，再向鏈表中添加元素就會觸發(fā)轉(zhuǎn)化。

以上就是我對于這個問題的理解。

本文轉(zhuǎn)載自微信公眾號「程序員的故事」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系程序員的故事公眾號。程序員的故事原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議。