您好,登錄后才能下訂單哦!
這篇文章主要介紹了Java8 HashMap擴(kuò)容算法實(shí)例解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
Java8的HashMap擴(kuò)容過程主要就是集中在resize()方法中
final Node<K,V>[] resize() { // ...省略不重要的 }
其中,當(dāng)HashMap擴(kuò)容完畢之后,需要對(duì)原有的數(shù)據(jù)進(jìn)行轉(zhuǎn)移。因?yàn)槿萘孔兇罅?,部分元素的位置因此要變更,因而出現(xiàn)了下面的這個(gè)轉(zhuǎn)移過程。
轉(zhuǎn)移過程大致是:依次從舊數(shù)組里取值,然后從該值對(duì)應(yīng)的鏈表上依次取出節(jié)點(diǎn),對(duì)節(jié)點(diǎn)取模分別放入lo鏈表和hi鏈表,當(dāng)鏈表中節(jié)點(diǎn)遍歷完后,分別把lo鏈表和hi鏈表放入新數(shù)組的不同位置。
在看到如下第15行時(shí),我在想,為什么(e.hash & oldCap)== 0時(shí)就放入lo鏈表,否則就是hi鏈表?
說到這個(gè)問題,那我們就要回顧下HashMap存入新元素的過程了??聪旅娴牡?5行,可以發(fā)現(xiàn)插入時(shí)是使用(n - 1) & hash來計(jì)算位置的,即數(shù)組長(zhǎng)度-1,而擴(kuò)容移位是使用數(shù)組長(zhǎng)度n計(jì)算的,那這是為什么呢?
for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ...省略不重要的 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // ...省略不重要的 }
像我們看Java8的HashMap源碼,應(yīng)該都應(yīng)該知道HashMap的底層數(shù)組長(zhǎng)度都是2的n方的值
那么我們就假設(shè)一個(gè)底層數(shù)組長(zhǎng)度為8的HashMap模擬進(jìn)行插入元素和擴(kuò)容移位的過程
長(zhǎng)度n=8 ----> 0x1000
n-1 ----> 0x0111
此時(shí)寫入兩個(gè)元素,兩個(gè)元素的hash值分別為hash2 = 0x0101,hash3 = 0x1101
hash2 & n-1 = 0x0101
hash3 & n-1 = 0x0101
兩個(gè)hash取模后的結(jié)果是一致的,所以它們會(huì)在同一個(gè)地方組成鏈表
那么此時(shí)如果要進(jìn)行擴(kuò)容移位呢?
hash2 & n = 0x0000
hash3 & n = 0x1000
此時(shí)兩者的結(jié)果是不一樣的,并且相差0x1000即10進(jìn)制的8即數(shù)組長(zhǎng)度.。
所以這也就是為什么上圖15行只判斷==0的原因,因?yàn)檫@個(gè)取模結(jié)果只有0和1兩種值(數(shù)組長(zhǎng)度是2的n次方,只有除了符號(hào)位外的最高位為1)
而兩個(gè)取模結(jié)果等于數(shù)組長(zhǎng)度,這也就是為什么上圖第32和36行那么處理的原因。
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。