微信搜索??「碼農(nóng)田小齊」巩掺，關(guān)注這個(gè)在紐約的程序媛贼穆，回復(fù)「01-05」可以獲取計(jì)算機(jī)精選書籍、個(gè)人刷題筆記坯临、大廠面經(jīng)焊唬、面試資料等資源，么么噠～
哈希沖突詳解
一般來說哈希沖突有兩大類解決方式
- Separate chaining
- Open addressing
Java 中采用的是第一種 Separate chaining看靠，即在發(fā)生碰撞的那個(gè)桶后面再加一條“鏈”來存儲(chǔ)赶促，那么這個(gè)“鏈”使用的具體是什么數(shù)據(jù)結(jié)構(gòu)，不同的版本稍有不同：
在 JDK1.6 和 1.7 中挟炬，是用鏈表存儲(chǔ)的鸥滨，這樣如果碰撞很多的話，就變成了在鏈表上的查找谤祖，worst case 就是 O(n)婿滓；
在 JDK 1.8 進(jìn)行了優(yōu)化，當(dāng)鏈表長(zhǎng)度較大時(shí)（超過 8）粥喜，會(huì)采用紅黑樹來存儲(chǔ)凸主，這樣大大提高了查找效率。
（話說容客，這個(gè)還真的喜歡考秕铛，已經(jīng)在多次面試中被問過了，還有面試官問為什么是超過“8”才用紅黑樹??）
第二種方法 open addressing 也是非常重要的思想缩挑，因?yàn)樵谡鎸?shí)的分布式系統(tǒng)里，有很多地方會(huì)用到 hash 的思想但又不適合用 seprate chaining鬓梅。
這種方法是順序查找供置，如果這個(gè)桶里已經(jīng)被占了，那就按照“某種方式”繼續(xù)找下一個(gè)沒有被占的桶绽快，直到找到第一個(gè)空的芥丧。
如圖所示，John Smith 和 Sandra Dee 發(fā)生了哈希沖突坊罢，都被計(jì)算到 152 號(hào)桶续担，于是 Sandra 就去了下一個(gè)空位 - 153 號(hào)桶，當(dāng)然也會(huì)對(duì)之后的 key 發(fā)生影響：Ted Baker 計(jì)算結(jié)果本應(yīng)是放在 153 號(hào)的活孩，但鑒于已經(jīng)被 Sandra 占了物遇，就只能再去下一個(gè)空位了，所以到了 154 號(hào)。
這種方式叫做 Linear probing 線性探查询兴，就像上圖所示乃沙，一個(gè)個(gè)的順著找下一個(gè)空位。當(dāng)然還有其他的方式诗舰，比如去找平方數(shù)警儒，或者 Double hashing.
如果你喜歡這篇文章，記得給我點(diǎn)贊留言哦～你們的支持和認(rèn)可眶根，就是我創(chuàng)作的最大動(dòng)力蜀铲，我們下篇文章見！
我是小齊属百，紐約程序媛蝙茶，終生學(xué)習(xí)者，每天晚上 9 點(diǎn)诸老，云自習(xí)室里不見不散隆夯！
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE
