1 什么是hash沖突

我們知道HashMap底層是由數(shù)組+鏈表/紅黑樹構(gòu)成的，當(dāng)我們通過put(key, value)向hashmap中添加元素時，需要通過散列函數(shù)確定元素究竟應(yīng)該放置在數(shù)組中的哪個位置，當(dāng)不同的元素被放置在了數(shù)據(jù)的同一個位置時，后放入的元素會以鏈表的形式，插在前一個元素的尾部，這個時候我們稱發(fā)生了hash沖突。

2 如何解決hash沖突

事實上，想讓hash沖突完全不發(fā)生，是不太可能的，我們能做的只是盡可能的降低hash沖突發(fā)生的概率：下面介紹在HashMap中是如何應(yīng)對hash沖突的?

當(dāng)我們向hashmap中put元素(key, value)時,最終會執(zhí)行putVal()方法，而在putVal()方法中，又執(zhí)行了hash(key)這個操作，并將執(zhí)行結(jié)果作為參數(shù)傳遞給了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í)行結(jié)果
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(h = key.hashCode()) ^ (h >>> 16)執(zhí)行了三步操作 ：我們一步一步來分析:

第1步：h = key.hashCode()

這一步會根據(jù)key值計算出一個int類型的h值也就是hashcode值，例如

"helloWorld".hashCode() --> -1554135584
"123456".hashCode() --> 1450575459
"我愛java".hashCode() --> -1588929438

至于hashCode()是如何根據(jù)key計算出hashcode值的，要分幾種情況進(jìn)行分析:

1. 如果我們使用的自己創(chuàng)建的對象，在我們沒有重寫hashCode()方法的情況下,會調(diào)用Object類的hashCode()方法，而此時返回就是對象的內(nèi)存地址值，所以如果對象不同，那么通過hashcode()計算出的hashcode就是不同的。
2. 如果是使用java中定義的引用類型例如String，Integer等作為key，這些類一般都會重寫hashCode()方法，有興趣可以翻看一下對應(yīng)的源碼。簡單來說，Integer類的hashCode()返回的就是Integer值,而String類型的hashCode()方法稍稍復(fù)雜一點，這里不做展開?？偟膩碚f，hashCode()方法的作用就是要根據(jù)不同的key得到不同的hashCode值。

第2步：h >>> 16

這一步將第1步計算出的h值無符號右移16位。

為什么要右移16位，當(dāng)然是位了第三步的操作。

第3步：h ^ (h >>> 16)

將hashcode值的高低16位進(jìn)行異或操作(同0得0、同1得0、不同得1)得到hash值，舉例說明：

• 假設(shè)h值為：1290846991
• 它的二進(jìn)制數(shù)為：01001100 11110000 11000011 00001111
• 右移十六位之后：00000000 00000000 01001100 11110000
• 進(jìn)行異或操作后：01001100 11110000 10001100 11110000
• 最終得到的hash值：1290833136

那么問題來了: 明明通過第一步得到的hashcode值就可以作為hash返回，為什么還要要進(jìn)行第二步和第三步的操作呢？答案是為了減少hash沖突，另外，最新面試題整理好了，點擊Java面試庫小程序在線刷題。

元素在數(shù)組中存放的位置是由下面這行代碼決定的：

// 將(數(shù)組的長度-1)和hash值進(jìn)行按位與操作:
i = (n - 1) & hash  // i為數(shù)組對應(yīng)位置的索引  n為當(dāng)前數(shù)組的大小

我們將上面這步操作作為第4步操作，來對比一下執(zhí)行1、2、3、4四個步驟和只執(zhí)行第1、4兩個步驟所產(chǎn)生的不同效果。

我們向hashmap中put兩個元素node1(key1, value1)、node2(key2, value2)，hashmap的數(shù)組長度n=16。

執(zhí)行1、2、3、4 四個步驟:

1.h = key.hashCode()

• 假設(shè)計算的結(jié)果為：h = 3654061296
• 對應(yīng)的二進(jìn)制數(shù)為: ???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 對應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111
• hash : ??01101100 11110000 11100000 00000110
• hash & 15 : ?? 00000000 00000000 00000000 00000110
• 轉(zhuǎn)化為10進(jìn)制 ：&ensp 5

最終得到i的值為5，也就是說node1存放在數(shù)組索引為5的位置。

同理我們對(key2, value2) 進(jìn)行上述同樣的操作過程:

1.h = key.hashCode()

• 假設(shè)計算的結(jié)果為：h = 3652881648
• 對應(yīng)的二進(jìn)制數(shù)為: ???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 對應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111
• hash : ??01101100 11110000 11100000 00101101
• hash & 15 : ??00000000 00000000 00000000 00001101
• 轉(zhuǎn)化為10進(jìn)制 ：&ensp 13

最終得到i的值為13，也就是說node2存放在數(shù)組索引為13的位置

node1和node2存儲的位置如下圖所示:

執(zhí)行1、4兩個步驟。另外，最新面試題整理好了，點擊Java面試庫小程序在線刷題。

1.h = key.hashCode()

• 計算的結(jié)果同樣為：h = 3654061296
• 對應(yīng)的二進(jìn)制數(shù)為: ???01101100 11100110 10001100 11110000

4.i = (n-1) & hash

• n-1=15 對應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111
• hash(h) : ??01101100 11100110 10001100 11110000
• hash & 15 : ??00000000 00000000 00000000 00000000
• 轉(zhuǎn)化為10進(jìn)制 ：? 0

最終得到i的值為0，也就是說node1存放在數(shù)組索引為0的位置

同理我們對(key2, value2) 進(jìn)行上述同樣的操作過程:

1.h = key.hashCode()

• 計算的結(jié)果同樣為：h = 3652881648
• 對應(yīng)的二進(jìn)制數(shù)為: ???01101100 11011101 10001100 11110000

4.i = (n-1) & hash

• n-1=15 對應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111
• hash(h) : ??01101100 11110000 11100000 11110000
• hash & 15 : ??00000000 00000000 00000000 00000000
• 轉(zhuǎn)化為10進(jìn)制 ：? 0

最終得到i的值為0，也就是說node2同樣存放在數(shù)組索引為0的位置

node1和node2存儲的位置如下圖所示:

相信大家已經(jīng)看出區(qū)別了。關(guān)注Java核心技術(shù)，推送更多 Java 干貨！

當(dāng)數(shù)組長度n較小時，n-1的二進(jìn)制數(shù)高16位全部位0，這個時候如果直接和h值進(jìn)行&（按位與）操作，那么只能利用到h值的低16位數(shù)據(jù)，這個時候會大大增加hash沖突發(fā)生的可能性，因為不同的h值轉(zhuǎn)化為2進(jìn)制后低16位是有可能相同的。

如上面所舉例子中:key1.hashCode() 和key2.hashCode() 得到的h值不同，一個h1 = 3654061296 ，另一個h2 = 3652881648，但是不幸的是這h1、h2兩個數(shù)轉(zhuǎn)化為2進(jìn)制后低16位是完全相同的，所以h1 & (n-1)和 h2 & (n-1) 會計算出相同的結(jié)果，這也導(dǎo)致了node1和node2 存儲在了數(shù)組索引相同的位置，發(fā)生了hash沖突。

當(dāng)我們使用進(jìn)行 h ^ (h >>> 16) 操作時，會將h的高16位數(shù)據(jù)和低16位數(shù)據(jù)進(jìn)行異或操作，最終得出的hash值的高16位保留了h值的高16位數(shù)據(jù)，而hash值的低16數(shù)據(jù)則是h值的高低16位數(shù)據(jù)共同作用的結(jié)果。所以即使h1和h2的低16位相同，最終計算出的hash值低16位也大概率是不同的，降低了hash沖突發(fā)生的概率。

ps：這里面還有一個值的注意的點: 為什么是(n-1)?

JDK 8 系列教程：https://www.javastack.cn/categories/Java/Java8/

我們知道n是hashmap中數(shù)組的長度,那么為要進(jìn)行n-1的操作？答案同樣是為了降低hash沖突發(fā)生的概率！

要理解這一點，我們首先要知道HashMap規(guī)定了數(shù)組的長度n必須為2的整數(shù)次冪，至于為什么是2的整數(shù)次冪，會在HashMap的擴(kuò)容方法resize()里詳細(xì)講。

既然n為2的整數(shù)次冪，那么n一定是一個偶數(shù)。那么我們來比較i = hash & n和 i = hash & (n-1)有什么異同。

n為偶數(shù)，那么n轉(zhuǎn)化為2進(jìn)制后最低位一定為0，與hash進(jìn)行按位與操作后最低位仍一定為0，這就導(dǎo)致i值只能為偶數(shù)，這樣就浪費(fèi)了數(shù)組中索引為奇數(shù)的空間，同時也增加了hash沖突發(fā)生的概率。

所以我們要執(zhí)行n-1,得到一個奇數(shù)，這樣n-1轉(zhuǎn)化為二進(jìn)制后低位一定為1，與hash進(jìn)行按位與操作后最低位即可能位0也可能位1，這就是使得i值即可能為偶數(shù)，也可能為奇數(shù)，充分利用了數(shù)組的空間，降低hash沖突發(fā)生的概率。

至此, JDK1.8中 HashMap 是如何在存儲元素時減少hash發(fā)生就講解完畢了！

來源：blog.csdn.net/weixin_43689776/article/details/99999126

END

推薦閱讀

一鍵生成Springboot & Vue項目！【畢設(shè)神器】

Java可視化編程工具系列（一）

Java可視化編程工具系列（二）

順便給大家推薦一個GitHub項目，這個 GitHub 整理了上千本常用技術(shù)PDF，絕大部分核心的技術(shù)書籍都可以在這里找到，
GitHub地址：https://github.com/javadevbooks/books
電子書已經(jīng)更新好了，你們需要的可以自行下載了，記得點一個star，持續(xù)更新中..