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); }

我們一步一步來分析

• 第1步：h = key.hashCode()

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

• 第2步：h >>> 16
  無符號(hào)右移(>>>)：
  對(duì)于正數(shù)的帶符號(hào)右移，不論正數(shù)還是負(fù)數(shù)，移位過程中高位均補(bǔ)零。
  

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

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

• 第四步：計(jì)算元素在數(shù)組中存放的位置
  由下面這行代碼決定的：

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

我們將上面這步操作作為第4步操作，來對(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è)步驟:

h = key.hashCode()
假設(shè)計(jì)算的結(jié)果為：h = 3654061296
對(duì)應(yīng)的二進(jìn)制數(shù)為: ???01101100 11100110 10001100 11110000

h >>> 16
h無符號(hào)右移16位得到： 00000000 00000000 01101100 11100110

hash = h ^ (h >>> 16)
異或操作后得到hash：? 01101100 11110000 11100000 00000110

i = (n-1) & hash
n-1=15 對(duì)應(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的位置。

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

h = key.hashCode()
假設(shè)計(jì)算的結(jié)果為：h = 3652881648
對(duì)應(yīng)的二進(jìn)制數(shù)為: ???01101100 11011101 10001100 11110000

h >>> 16
h無符號(hào)右移16位得到： 00000000 00000000 01101100 11011101

hash = h ^ (h >>> 16)
異或操作后得到hash：? 01101100 11110000 11100000 00101101

i = (n-1) & hash
n-1=15 對(duì)應(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的位置

執(zhí)行1、4兩個(gè)步驟:

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

i = (n-1) & hash
n-1=15 對(duì)應(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的位置

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

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

i = (n-1) & hash
n-1=15 對(duì)應(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的位置

相信大家已經(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ù)。那么我們來比較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ā)生的概率。

總結(jié)

以上是生活随笔為你收集整理的jdk1.8hashmap为什么对hash进行了一次扰动处理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。