常用數據結構基本上是面試必問的問題，比如HashMap、LinkList、ConcurrentHashMap等。

關於HashMap，有個學員私信了我一個面試題說：「HashMap是怎麼解決哈希衝突的？」

關於這個問題，我們來模擬一下普通人和高手對於這個問題的回答。

普通人：

嗯…. HashMap我好久之前看過它的源碼，我記得好像是通過鏈表來解決的！

高手：

嗯，這個問題我從四個方面來回答。

1.要了解Hash衝突，那首先我們要先了解Hash演算法和Hash表。

（1）Hash演算法，就是把任意長度的輸入，通過散列演算法，變成固定長度的輸出，這個輸出結果是散列值。

（2）Hash表又叫做「散列表」，它是通過key直接訪問在記憶體存儲位置的數據結構，在具體實現上，我們通過hash函數把key映射到表中的某個位置，來獲取這個位置的數據，從而加快查找速度。

2.所謂hash衝突，是由於哈希演算法被計算的數據是無限的，而計算後的結果範圍有限，所以總會存在不同的數據經過計算後得到的值相同，這就是哈希衝突。

3.通常解決hash衝突的方法有4種。

（1）開放定址法，也稱為線性探測法，就是從發生衝突的那個位置開始，按照一定的次序從hash表中找到一個空閑的位置，然後把發生衝突的元素存入到這個空閑位置中。ThreadLocal就用到了線性探測法來解決hash衝突的。

向這樣一種情況

在hash表索引1的位置存了一個key=name，當再次添加key=hobby時，hash計算得到的索引也是1，這個就是hash衝突。而開放定址法，就是按順序向前找到一個空閑的位置來存儲衝突的key。

（2）鏈式定址法，這是一種非常常見的方法，簡單理解就是把存在hash衝突的key，以單向鏈表的方式來存儲，比如HashMap就是採用鏈式定址法來實現的。

向這樣一種情況

存在衝突的key直接以單向鏈表的方式進行存儲。

（3）再hash法，就是當通過某個hash函數計算的key存在衝突時，再用另外一個hash函數對這個key做hash，一直運算直到不再產生衝突。這種方式會增加計算時間，性能影響較大。

（4）建立公共溢出區，就是把hash表分為基本表和溢出表兩個部分，凡事存在衝突的元素，一律放入到溢出表中。

4.HashMap在JDK1.8版本中，通過鏈式定址法+紅黑樹的方式來解決hash衝突問題，其中紅黑樹是為了優化Hash錶鏈表過長導致時間複雜度增加的問題。當鏈表長度大於8並且hash表的容量大於64的時候，再向鏈表中添加元素就會觸發轉化。

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

這道面試題主要考察Java基礎，面向的範圍是工作1到5年甚至5年以上。

因為集合類的對象在項目中使用頻率較高，如果對集合理解不夠深刻，容易在項目中製造隱藏的BUG。

所以，再強調一下，面試的時候，基礎是很重要的考核項！！

本期的普通人VS高手面試系列的就到這裡結束了，需要面試資料或者面試問題諮詢歡迎私信和評論區留言。

我是Mic，一個工作了14年的Java程式設計師，咱們下期再見。