微信搜索🔍「碼農田小齊」，關注這個在紐約的程序媛，回復「01-05」可以獲取計算機精選書籍、個人刷題筆記、大廠面經、面試資料等資源，么么噠～

哈希衝突詳解

一般來說哈希衝突有兩大類解決方式^[1]

1. Separate chaining
2. Open addressing

Java 中採用的是第一種 Separate chaining，即在發生碰撞的那個桶後面再加一條「鏈」來存儲，那麼這個「鏈」使用的具體是什麼數據結構，不同的版本稍有不同：

在 JDK1.6 和 1.7 中，是用鏈表存儲的，這樣如果碰撞很多的話，就變成了在鏈表上的查找，worst case 就是 O(n)；

在 JDK 1.8 進行了優化，當鏈表長度較大時（超過 8），會採用紅黑樹來存儲，這樣大大提高了查找效率。

（話說，這個還真的喜歡考，已經在多次面試中被問過了，還有面試官問為什麼是超過「8」才用紅黑樹🤔）

第二種方法 open addressing 也是非常重要的思想，因為在真實的分佈式系統里，有很多地方會用到 hash 的思想但又不適合用 seprate chaining。

這種方法是順序查找，如果這個桶里已經被佔了，那就按照「某種方式」繼續找下一個沒有被占的桶，直到找到第一個空的。

如圖所示，John Smith 和 Sandra Dee 發生了哈希衝突，都被計算到 152 號桶，於是 Sandra 就去了下一個空位 – 153 號桶，當然也會對之後的 key 發生影響：Ted Baker 計算結果本應是放在 153 號的，但鑒於已經被 Sandra 佔了，就只能再去下一個空位了，所以到了 154 號。

這種方式叫做 Linear probing 線性探查，就像上圖所示，一個個的順着找下一個空位。當然還有其他的方式，比如去找平方數，或者 Double hashing.

如果你喜歡這篇文章，記得給我點贊留言哦～你們的支持和認可，就是我創作的最大動力，我們下篇文章見！

我是小齊，紐約程序媛，終生學習者，每天晚上 9 點，雲自習室里不見不散！

更多乾貨文章見我的 Github: //github.com/xiaoqi6666/NYCSDE

參考資料