JDK1.8 中 HashMap 如何應(yīng)對(duì) hash 沖突？
來(lái)源：blog.csdn.net/weixin_43689776/
article/details/99999126
1 什么是hash沖突
我們知道HashMap底層是由數(shù)組+鏈表/紅黑樹(shù)構(gòu)成的，當(dāng)我們通過(guò)put(key, value)向hashmap中添加元素時(shí)，需要通過(guò)散列函數(shù)確定元素究竟應(yīng)該放置在數(shù)組中的哪個(gè)位置，當(dāng)不同的元素被放置在了數(shù)據(jù)的同一個(gè)位置時(shí)，后放入的元素會(huì)以鏈表的形式，插在前一個(gè)元素的尾部，這個(gè)時(shí)候我們稱(chēng)發(fā)生了hash沖突。
2 如何解決hash沖突
事實(shí)上，想讓hash沖突完全不發(fā)生，是不太可能的，我們能做的只是盡可能的降低hash沖突發(fā)生的概率：下面介紹在HashMap中是如何應(yīng)對(duì)hash沖突的?
當(dāng)我們向hashmap中put元素(key, value)時(shí),最終會(huì)執(zhí)行putVal()方法，而在putVal()方法中，又執(zhí)行了hash(key)這個(gè)操作，并將執(zhí)行結(jié)果作為參數(shù)傳遞給了putVal方法。那么我們先來(lái)看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í)行了三步操作 ：我們一步一步來(lái)分析:
第1步：h = key.hashCode()
這一步會(huì)根據(jù)key值計(jì)算出一個(gè)int類(lèi)型的h值也就是hashcode值，例如
"helloWorld".hashCode()?-->?-1554135584
"123456".hashCode()?-->?1450575459
"我愛(ài)java".hashCode()?-->?-1588929438
至于hashCode()是如何根據(jù)key計(jì)算出hashcode值的，要分幾種情況進(jìn)行分析:
如果我們使用的自己創(chuàng)建的對(duì)象，在我們沒(méi)有重寫(xiě)hashCode()方法的情況下,會(huì)調(diào)用Object類(lèi)的hashCode()方法，而此時(shí)返回就是對(duì)象的內(nèi)存地址值，所以如果對(duì)象不同，那么通過(guò)hashcode()計(jì)算出的hashcode就是不同的。
如果是使用java中定義的引用類(lèi)型例如String，Integer等作為key，這些類(lèi)一般都會(huì)重寫(xiě)hashCode()方法，有興趣可以翻看一下對(duì)應(yīng)的源碼。簡(jiǎn)單來(lái)說(shuō)，Integer類(lèi)的hashCode()返回的就是Integer值,而String類(lèi)型的hashCode()方法稍稍復(fù)雜一點(diǎn)，這里不做展開(kāi)?？偟膩?lái)說(shuō)，hashCode()方法的作用就是要根據(jù)不同的key得到不同的hashCode值。
第2步：h >>> 16
這一步將第1步計(jì)算出的h值無(wú)符號(hào)右移16位。
為什么要右移16位，當(dāng)然是位了第三步的操作。
第3步：h ^ (h >>> 16)
將hashcode值的高低16位進(jìn)行異或操作(同0得0、同1得0、不同得1)得到hash值，舉例說(shuō)明：
假設(shè)h值為：1290846991 它的二進(jìn)制數(shù)為：01001100 11110000 11000011 00001111 右移十六位之后：00000000 00000000 01001100 11110000 進(jìn)行異或操作后：01001100 11110000 10001100 11110000 最終得到的hash值：1290833136
那么問(wèn)題來(lái)了: 明明通過(guò)第一步得到的hashcode值就可以作為hash返回，為什么還要要進(jìn)行第二步和第三步的操作呢？答案是為了減少hash沖突！
元素在數(shù)組中存放的位置是由下面這行代碼決定的：
//?將(數(shù)組的長(zhǎng)度-1)和hash值進(jìn)行按位與操作:
i?=?(n?-?1)?&?hash??//?i為數(shù)組對(duì)應(yīng)位置的索引??n為當(dāng)前數(shù)組的大小
我們將上面這步操作作為第4步操作，來(lái)對(duì)比一下執(zhí)行1、2、3、4四個(gè)步驟和只執(zhí)行第1、4兩個(gè)步驟所產(chǎn)生的不同效果。
我們向hashmap中put兩個(gè)元素node1(key1, value1)、node2(key2, value2)，hashmap的數(shù)組長(zhǎng)度n=16。
執(zhí)行1、2、3、4 四個(gè)步驟:
1.h = key.hashCode()
假設(shè)計(jì)算的結(jié)果為： h = 3654061296對(duì)應(yīng)的二進(jìn)制數(shù)為: ??? 01101100 11100110 10001100 11110000
2.h >>> 16
h無(wú)符號(hào)右移16位得到： 00000000 00000000 01101100 11100110
3.hash = h ^ (h >>> 16)
異或操作后得到hash：? 01101100 11110000 11100000 00000110
4.i = (n-1) & hash
n-1=15 對(duì)應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111hash : ?? 01101100 11110000 11100000 00000110hash & 15 : ?? 00000000 00000000 00000000 00000110轉(zhuǎn)化為10進(jìn)制 ： &ensp 5
最終得到i的值為5，也就是說(shuō)node1存放在數(shù)組索引為5的位置。
同理我們對(duì)(key2, value2) 進(jìn)行上述同樣的操作過(guò)程:
1.h = key.hashCode()
假設(shè)計(jì)算的結(jié)果為： h = 3652881648對(duì)應(yīng)的二進(jìn)制數(shù)為: ??? 01101100 11011101 10001100 11110000
2.h >>> 16
h無(wú)符號(hào)右移16位得到： 00000000 00000000 01101100 11011101
3.hash = h ^ (h >>> 16)
異或操作后得到hash：? 01101100 11110000 11100000 00101101
4.i = (n-1) & hash
n-1=15 對(duì)應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111hash : ?? 01101100 11110000 11100000 00101101hash & 15 : ?? 00000000 00000000 00000000 00001101轉(zhuǎn)化為10進(jìn)制 ： &ensp 13
最終得到i的值為13，也就是說(shuō)node2存放在數(shù)組索引為13的位置
node1和node2存儲(chǔ)的位置如下圖所示:
執(zhí)行1、4兩個(gè)步驟:
1.h = key.hashCode()
計(jì)算的結(jié)果同樣為： h = 3654061296對(duì)應(yīng)的二進(jìn)制數(shù)為: ??? 01101100 11100110 10001100 11110000
4.i = (n-1) & hash
n-1=15 對(duì)應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111hash(h) : ?? 01101100 11100110 10001100 11110000hash & 15 : ?? 00000000 00000000 00000000 00000000轉(zhuǎn)化為10進(jìn)制 ：? 0
最終得到i的值為0，也就是說(shuō)node1存放在數(shù)組索引為0的位置
同理我們對(duì)(key2, value2) 進(jìn)行上述同樣的操作過(guò)程:
1.h = key.hashCode()
計(jì)算的結(jié)果同樣為： h = 3652881648對(duì)應(yīng)的二進(jìn)制數(shù)為: ??? 01101100 11011101 10001100 11110000
4.i = (n-1) & hash
n-1=15 對(duì)應(yīng)二進(jìn)制數(shù) : ?? 00000000 00000000 00000000 00001111hash(h) : ?? 01101100 11110000 11100000 11110000hash & 15 : ?? 00000000 00000000 00000000 00000000轉(zhuǎn)化為10進(jìn)制 ：? 0
最終得到i的值為0，也就是說(shuō)node2同樣存放在數(shù)組索引為0的位置
node1和node2存儲(chǔ)的位置如下圖所示:
相信大家已經(jīng)看出區(qū)別了：
當(dāng)數(shù)組長(zhǎng)度n較小時(shí)，n-1的二進(jìn)制數(shù)高16位全部位0，這個(gè)時(shí)候如果直接和h值進(jìn)行&（按位與）操作，那么只能利用到h值的低16位數(shù)據(jù)，這個(gè)時(shí)候會(huì)大大增加hash沖突發(fā)生的可能性，因?yàn)椴煌膆值轉(zhuǎn)化為2進(jìn)制后低16位是有可能相同的，如上面所舉例子中:key1.hashCode() 和key2.hashCode() 得到的h值不同，一個(gè)h1 = 3654061296 ，另一個(gè)h2 = 3652881648，但是不幸的是這h1、h2兩個(gè)數(shù)轉(zhuǎn)化為2進(jìn)制后低16位是完全相同的，所以h1 & (n-1)和 h2 & (n-1) 會(huì)計(jì)算出相同的結(jié)果，這也導(dǎo)致了node1和node2 存儲(chǔ)在了數(shù)組索引相同的位置，發(fā)生了hash沖突。
當(dāng)我們使用進(jìn)行 h ^ (h >>> 16) 操作時(shí)，會(huì)將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位相同，最終計(jì)算出的hash值低16位也大概率是不同的，降低了hash沖突發(fā)生的概率。
ps：這里面還有一個(gè)值的注意的點(diǎn): 為什么是(n-1)?
我們知道n是hashmap中數(shù)組的長(zhǎng)度,那么為要進(jìn)行n-1的操作？答案同樣是為了降低hash沖突發(fā)生的概率！
要理解這一點(diǎn)，我們首先要知道HashMap規(guī)定了數(shù)組的長(zhǎng)度n必須為2的整數(shù)次冪，至于為什么是2的整數(shù)次冪，會(huì)在HashMap的擴(kuò)容方法resize()里詳細(xì)講。
既然n為2的整數(shù)次冪，那么n一定是一個(gè)偶數(shù)。那么我們來(lái)比較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ù)的空間，同時(shí)也增加了hash沖突發(fā)生的概率。
所以我們要執(zhí)行n-1,得到一個(gè)奇數(shù)，這樣n-1轉(zhuǎn)化為二進(jìn)制后低位一定為1，與hash進(jìn)行按位與操作后最低位即可能位0也可能位1，這就是使得i值即可能為偶數(shù)，也可能為奇數(shù)，充分利用了數(shù)組的空間，降低hash沖突發(fā)生的概率。
至此, JDK1.8中 HashMap 是如何在存儲(chǔ)元素時(shí)減少hash發(fā)生就講解完畢了！
如有文章對(duì)你有幫助，
“在看”和轉(zhuǎn)發(fā)是對(duì)我最大的支持！
一款牛逼的Java面試題庫(kù)，點(diǎn)擊下圖查看詳細(xì)內(nèi)容
