面試題：HashMap 是怎么解決哈希沖突的？
前言
今天來分享一道比較好的面試題，“HashMap 是怎么解決哈希沖突的？”對于這個問題，我們一起看看考察點和比較好的回答吧！
考察點
現在的企業級開發中HashMap幾乎是最常用到的容器，了解HashMap 是怎么解決哈希沖突的，有助于我們開發出更加優秀的代碼。那么這個問題就是面試官想考察我們是不是平日里善于積累，仔細思考這方面的知識！
回答
關于這個問題，我從三個方面來回答：
1.hash沖突的基礎就是hash算法和hash表這種數據結構。先講講hash算法和hash表。
①Hash 算法，就是通過散列算法，把任意長度的輸入變成固定長度的輸出。這個輸出就是散列值。
hashValue1 = hash(inputStr1);
hashValue2 = hash(inputStr2);
hashValue1和hashValue2的長度一樣②Hash 表又叫做“散列表”，其本質是通過key，可以直接訪問在內存存儲位置的數據結構。因此在表現上，我們可以通過hash函數把key映射到散列表中的某個位置，進而獲取這個位置的數據，這樣能夠加快查找速度。
③那么我們所說的hash 沖突，因為哈希算法計算的數據是無窮的，而計算的結果范圍是有限的，這樣就會造成不同的輸入得到的結果確實一樣的情況。也就是說發生了沖突。如圖所示：
2.如何結果hash沖突呢？這里講一下常用的4中方法。
①開放定址法，也被稱為線性探測法，其原理是這樣的，從發生沖突的那個位置開始，通過一定的次序從hash表里面找一個空閑的位置。之后將發生沖突的元素存入到這個空閑位置中。在應用上面，我們常見的ThreadLocal就是用到了線性探測法來解決hash沖突。如圖，在 hash 表索引 1 的位置存了一個 key=name，當再次添加key=hobby 時hash 計算得到的索引也是 1，這個就是 hash 沖突。而開放定址法，就是按順序向前找到一個空閑的位置來存儲沖突的 key。
②鏈式尋址法，這是一種非常常見的方法，簡單理解就是把存在 hash 沖突的 key，以單向鏈表的方式來存儲，比如 HashMap 就是采用鏈式尋址法來實現的。向這樣一種情況（如圖），存在沖突的 key 直接以單向鏈表的方式進行存儲。
③再 hash 法，就是當通過某個 hash 函數計算的 key 存在沖突時，再用另外一個 hash 函數對這個 key 做 hash，一直運算直到不再產生沖突。這種方式會增加計算時間，性能影響較大。
④. 建立公共溢出區， 就是把 hash 表分為基本表和溢出表兩個部分，凡是存在沖突的元素，一律放入到溢出表中。
3.HashMap 在 JDK1.8 版本中，通過鏈式尋址法+紅黑樹的方式來解決 hash 沖突問題，其中紅黑樹是為了優化 Hash 表鏈表過長導致時間復雜度增加的問題。當鏈表長度大于 8 并且 hash 表的容量大于 64 的時候，再向鏈表中添加元素就會觸發轉化。
以上就是我對于這個問題的理解。
本文轉載自微信公眾號「程序員的故事」，可以通過以下二維碼關注。轉載本文請聯系程序員的故事公眾號。程序員的故事原創文章，遵循CC 4.0 BY-SA版權協議。
