什么是hash沖突
我們知道HashMap底層是由數組+鏈表/紅黑樹構成的，當我們通過put(key, value)向hashmap中添加元素時古瓤，需要通過散列函數確定元素究竟應該放置在數組中的哪個位置赢织，當不同的元素被放置在了數據的同一個位置時，后放入的元素會以鏈表的形式馍盟，插在前一個元素的尾部于置，這個時候我們稱發(fā)生了hash沖突。
如何解決hash沖突
事實上贞岭，想讓hash沖突完全不發(fā)生八毯，是不太可能的，我們能做的只是盡可能的降低hash沖突發(fā)生的概率：下面介紹在HashMap中是如何應對hash沖突的?
當我們向hashmap中put元素(key, value)時,最終會執(zhí)行putVal()方法瞄桨，而在putVal()方法中话速，又執(zhí)行了hash(key)這個操作，并將執(zhí)行結果作為參數傳遞給了putVal方法芯侥。那么我們先來看hash(key)方法干了什么泊交。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
// 判斷key是否為null, 如果為null,則直接返回0;
// 如果不為null，則返回(h = key.hashCode()) ^ (h >>> 16)的執(zhí)行結果
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
(h = key.hashCode()) ^ (h >>> 16)執(zhí)行了三步操作 ：我們一步一步來分析:
第1步：h = key.hashCode()
這一步會根據key值計算出一個int類型的h值也就是hashcode值柱查，例如
"helloWorld".hashCode() --> -1554135584
"123456".hashCode() --> 1450575459
"我愛java".hashCode() --> -1588929438
至于hashCode()是如何根據key計算出hashcode值的廓俭，要分幾種情況進行分析:
- 如果我們使用的自己創(chuàng)建的對象，在我們沒有重寫hashCode()方法的情況下,會調用Object類的hashCode()方法唉工，而此時返回就是對象的內存地址值研乒，所以如果對象不同，那么通過hashcode()計算出的hashcode就是不同的淋硝。
- 如果是使用java中定義的引用類型例如String雹熬，Integer等作為key，這些類一般都會重寫hashCode()方法谣膳，有興趣可以翻看一下對應的源碼竿报。簡單來說，Integer類的hashCode()返回的就是Integer值,而String類型的hashCode()方法稍稍復雜一點参歹，這里不做展開仰楚。總的來說，hashCode()方法的作用就是要根據不同的key得到不同的hashCode值僧界。
第2步：h >>> 16
這一步將第1步計算出的h值無符號右移16位侨嘀。
為什么要右移16位，當然是位了第三步的操作捂襟。
第3步：h ^ (h >>> 16)
將hashcode值的高低16位進行異或操作(同0得0咬腕、同1得0、不同得1)得到hash值葬荷，舉例說明：
- 假設h值為：1290846991
- 它的二進制數為：01001100 11110000 11000011 00001111
- 右移十六位之后：00000000 00000000 01001100 11110000
- 進行異或操作后：01001100 11110000 10001100 11110000
- 最終得到的hash值：1290833136
那么問題來了: 明明通過第一步得到的hashcode值就可以作為hash返回涨共，為什么還要要進行第二步和第三步的操作呢？答案是為了減少hash沖突宠漩！
元素在數組中存放的位置是由下面這行代碼決定的：
// 將(數組的長度-1)和hash值進行按位與操作:
i = (n - 1) & hash // i為數組對應位置的索引 n為當前數組的大小
我們將上面這步操作作為第4步操作举反，來對比一下執(zhí)行1、2扒吁、3火鼻、4四個步驟和只執(zhí)行第1、4兩個步驟所產生的不同效果雕崩。
我們向hashmap中put兩個元素node1(key1, value1)魁索、node2(key2, value2)，hashmap的數組長度n=16盼铁。
執(zhí)行1粗蔚、2、3饶火、4 四個步驟:
1. h = key.hashCode()
- 假設計算的結果為：h = 3654061296
- 對應的二進制數為: ???01101100 11100110 10001100 11110000
2. h >>> 16
- h無符號右移16位得到：00000000 00000000 01101100 11100110
3. hash = h ^ (h >>> 16)
- 異或操作后得到hash：? 01101100 11110000 11100000 00000110
4. i = (n-1) & hash
- n-1=15 對應二進制數 : ?? 00000000 00000000 00000000 00001111
- hash : ??01101100 11110000 11100000 00000110
- hash & 15 : ?? 00000000 00000000 00000000 00000110
- 轉化為10進制 ：&ensp 5
最終得到i的值為5鹏控，也就是說node1存放在數組索引為5的位置。
同理我們對(key2, value2) 進行上述同樣的操作過程:
1. h = key.hashCode()
- 假設計算的結果為：h = 3652881648
- 對應的二進制數為: ???01101100 11011101 10001100 11110000
2. h >>> 16
- h無符號右移16位得到：00000000 00000000 01101100 11011101
3. hash = h ^ (h >>> 16)
- 異或操作后得到hash：? 01101100 11110000 11100000 00101101
4. i = (n-1) & hash
- n-1=15 對應二進制數 : ?? 00000000 00000000 00000000 00001111
- hash : ??01101100 11110000 11100000 00101101
- hash & 15 : ??00000000 00000000 00000000 00001101
- 轉化為10進制 ：&ensp 13
最終得到i的值為13趁窃，也就是說node2存放在數組索引為13的位置
node1和node2存儲的位置如下圖所示:
執(zhí)行1牧挣、4兩個步驟:
1. h = key.hashCode()
- 計算的結果同樣為：h = 3654061296
- 對應的二進制數為: ???01101100 11100110 10001100 11110000
4. i = (n-1) & hash
- n-1=15 對應二進制數 : ?? 00000000 00000000 00000000 00001111
- hash(h) : ??01101100 11100110 10001100 11110000
- hash & 15 : ??00000000 00000000 00000000 00000000
- 轉化為10進制 ：? 0
最終得到i的值為0，也就是說node1存放在數組索引為0的位置
同理我們對(key2, value2) 進行上述同樣的操作過程:
1. h = key.hashCode()
- 計算的結果同樣為：h = 3652881648
- 對應的二進制數為: ???01101100 11011101 10001100 11110000
4. i = (n-1) & hash
- n-1=15 對應二進制數 : ?? 00000000 00000000 00000000 00001111
- hash(h) : ??01101100 11110000 11100000 11110000
- hash & 15 : ??00000000 00000000 00000000 00000000
- 轉化為10進制 ：? 0
最終得到i的值為0醒陆，也就是說node2同樣存放在數組索引為0的位置
node1和node2存儲的位置如下圖所示:
相信大家已經看出區(qū)別了：
當數組長度n較小時瀑构，n-1的二進制數高16位全部位0，這個時候如果直接和h值進行&（按位與）操作刨摩，那么只能利用到h值的低16位數據寺晌，這個時候會大大增加hash沖突發(fā)生的可能性，因為不同的h值轉化為2進制后低16位是有可能相同的澡刹，如上面所舉例子中:key1.hashCode() 和key2.hashCode() 得到的h值不同呻征，一個h1 = 3654061296 ，另一個h2 = 3652881648罢浇，但是不幸的是這h1陆赋、h2兩個數轉化為2進制后低16位是完全相同的沐祷，所以h1 & (n-1)和 h2 & (n-1) 會計算出相同的結果，這也導致了node1和node2 存儲在了數組索引相同的位置攒岛，發(fā)生了hash沖突赖临。
當我們使用進行 h ^ (h >>> 16) 操作時，會將h的高16位數據和低16位數據進行異或操作灾锯，最終得出的hash值的高16位保留了h值的高16位數據兢榨，而hash值的低16數據則是h值的高低16位數據共同作用的結果。所以即使h1和h2的低16位相同顺饮，最終計算出的hash值低16位也大概率是不同的吵聪，降低了hash沖突發(fā)生的概率。
ps：這里面還有一個值的注意的點: 為什么是(n-1)?
我們知道n是hashmap中數組的長度,那么為要進行n-1的操作兼雄？答案同樣是為了降低hash沖突發(fā)生的概率吟逝！
要理解這一點，我們首先要知道HashMap規(guī)定了數組的長度n必須為2的整數次冪赦肋，至于為什么是2的整數次冪澎办，會在HashMap的擴容方法resize()里詳細講。
既然n為2的整數次冪金砍，那么n一定是一個偶數。那么我們來比較i = hash & n和 i = hash & (n-1)有什么異同麦锯。
n為偶數恕稠，那么n轉化為2進制后最低位一定為0，與hash進行按位與操作后最低位仍一定為0扶欣，這就導致i值只能為偶數鹅巍，這樣就浪費了數組中索引為奇數的空間，同時也增加了hash沖突發(fā)生的概率料祠。
所以我們要執(zhí)行n-1,得到一個奇數骆捧，這樣n-1轉化為二進制后低位一定為1，與hash進行按位與操作后最低位即可能位0也可能位1髓绽，這就是使得i值即可能為偶數敛苇，也可能為奇數，充分利用了數組的空間顺呕，降低hash沖突發(fā)生的概率枫攀。
至此, JDK1.8中 HashMap 是如何在存儲元素時減少hash發(fā)生就講解完畢了！
轉載：https://blog.csdn.net/weixin_36380516/article/details/121484523
