導讀
前面文章
一、深入理解-Java集合初篇
中我們對Java的集合體系進行一個簡單的分析介紹，上兩篇文章
二、Jdk1。7和1。8中HashMap資料結構及原始碼分析
、
二、JDK1。7和1。8HashMap資料結構及原始碼分析-續
中我們分別對JDK1。7和JDK1。8中HashMap的資料結構、主要宣告變數、建構函式、HashMap的put操作方法做了深入的講解和原始碼分析。
三、深入理解Java中的HashMap「網易面試快答」
文章中主要針對面試中常見的檔案進行簡單解答。
本篇文章我們將要對JDK1.8中HashMap的雜湊衝突及減少雜湊衝突的解決方案做詳細的介紹，並透過原始碼加深大家的理解。
如果大家在面試中針對Java集合或者Java中的HashMap大家還有什麼疑問或者其他問題，可以評論區告訴我。
簡單介紹
JDK1。7——-》雜湊表，連結串列
JDK1。8——-》雜湊表，連結串列，紅黑樹——- JDK1。8之後，當連結串列長度超過8使用紅黑樹。
非執行緒安全
0.75的負載因子，擴容必須為原來的兩倍。
預設大小為16，傳入的初始大小必須為2的冪次方的值，如果不為也會變為2的冪次方的值。
根據HashCode儲存資料。
JDK1。8的雜湊衝突解決方案
hash函式是先拿到透過key 的hashcode，是32位的int值，然後讓hashcode的高16位和低16位進行異或操作。
/** * Computes key。hashCode（） and spreads （XORs） higher bits of hash * to lower。 Because the table uses power-of-two masking， sets of * hashes that vary only in bits above the current mask will * always collide。 （Among known examples are sets of Float keys * holding consecutive whole numbers in small tables。） So we * apply a transform that spreads the impact of higher bits * downward。 There is a tradeoff between speed， utility， and * quality of bit-spreading。 Because many common sets of hashes * are already reasonably distributed （so don‘t benefit from * spreading）， and because we use trees to handle large sets of * collisions in bins， we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage， as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds。 */ static final int hash（Object key） { int h； return （key == null） ？ 0 ： （h = key。hashCode（）） ^ （h >>> 16）； }
這個叫擾動函式，這麼設計有二點原因：
1. 一定要儘可能降低hash碰撞，越分散越好；
2. 演算法一定要儘可能高效，因為這是高頻操作, 因此採用位運算；
為什麼採用hashcode的高16位和低16位異或能降低hash碰撞？hash函式能不能直接用key的hashcode？
因為key。hashCode（）函式呼叫的是key鍵值型別自帶的雜湊函式，返回int型雜湊值。int值範圍為**-2147483648~2147483647**，前後加起來大概40億的對映空間。只要雜湊函式對映得比較均勻鬆散，一般應用是很難出現碰撞的。但問題是一個40億長度的陣列，記憶體是放不下的。你想，如果HashMap陣列的初始大小才16，用之前需要對陣列的長度取模運算，得到的餘數才能用來訪問陣列下標。（來自知乎-胖君）
原始碼中模運算就是把雜湊值和陣列長度-1做一個"與"操作，位運算比%運算要快。
bucketIndex = indexFor（hash， table。length）；static int indexFor（int h， int length） { return h & （length-1）；}
順便說一下，這也正好解釋了為什麼HashMap的陣列長度要取2的整數冪。因為這樣（陣列長度-1）正好相當於一個“低位掩碼”。“與”操作的結果就是雜湊值的高位全部歸零，只保留低位值，用來做陣列下標訪問。
以初始長度16為例，16-1=15。2進製表示是00000000 00000000 00001111。和某雜湊值做“與”操作如下，結果就是截取了最低的四位值。
10100101 11000100 00100101& 00000000 00000000 00001111—————————————————— 00000000 00000000 00000101 //高位全部歸零，只保留末四位
但這時候問題就來了，這樣就算我的雜湊值分佈再鬆散，要是隻取最後幾位的話，碰撞也會很嚴重。更要命的是如果雜湊本身做得不好，分佈上成等差數列的漏洞，如果正好讓最後幾個低位呈現規律性重複，就無比蛋疼。
時候“擾動函式”的價值就體現出來了，說到這裡大家應該猜出來了。看下面這個圖：
右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始雜湊碼的高位和低位，以此來加大低位的隨機性。而且混合後的低位摻雜了高位的部分特徵，這樣高位的資訊也被變相保留下來。
最後我們來看一下Peter Lawley的一篇專欄文章《An introduction to optimising a hashing strategy》裡的的一個實驗：他隨機選取了352個字串，在他們雜湊值完全沒有衝突的前提下，對它們做低位掩碼，取陣列下標。
結果顯示，
當HashMap陣列長度為512的時候（2的9次方），也就是用掩碼取低9位的時候，在沒有擾動函式的情況下，發生了103次碰撞，接近30%。而在使用了擾動函式之後只有92次碰撞。碰撞減少了將近10%。
看來擾動函式確實還是有功效的。
另外Java1.8相比1.7做了調整，1.7做了四次移位和四次異或，但明顯Java 8覺得擾動做一次就夠了，做4次的話，多了可能邊際效用也不大，所謂為了效率考慮就改成一次了。
1.7的hash程式碼：
static int hash（int h） { h ^= （h >>> 20） ^ （h >>> 12）； return h ^ （h >>> 7） ^ （h >>> 4）；}
1.8的hash程式碼：
static final int hash（Object key） { int h； return （key == null） ？ 0 ： （h = key。hashCode（）） ^ （h >>> 16）； }
往期文章連結
Java集合
一、深入理解-Java集合初篇
二、Jdk1。7和1。8中HashMap資料結構及原始碼分析
二、JDK1。7和1。8HashMap資料結構及原始碼分析-續
三、深入理解Java中的HashMap「網易面試快答」
Java-IO體系
一、JAVA IO/NIO體系介紹
二、網路IO原理-建立ServerSocket-徹底弄懂IO
三、JAVA中ServerSocket呼叫Linux系統核心
四、「大廠職員教你」IO進化過程之BIO
五、「大廠職員教你」Java-IO進化過程之NIO
六、Selector實現Netty中Reactor單執行緒模型
七、Selector實現Netty中Reactor主從模型
八、Netty入門服務端程式碼
九、IO進化過程之EVENT（EPOLL-事件驅動非同步模型）
如需瞭解更多更詳細內容也可關注本人CSDN部落格：
不吃_花椒
Java集合還需要學習的內容
