本篇文章為大家展示了如何解析Java8 HashMap擴容算法，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

成都創(chuàng)新互聯(lián)主營長嶺網(wǎng)站建設的網(wǎng)絡公司,主營網(wǎng)站建設方案,手機APP定制開發(fā),長嶺h5小程序定制開發(fā)搭建,長嶺網(wǎng)站營銷推廣歡迎長嶺等地區(qū)企業(yè)咨詢

Java8的HashMap擴容過程主要就是集中在resize()方法中

final Node<K,V>[] resize() {   // ...省略不重要的 }

其中，當HashMap擴容完畢之后，需要對原有的數(shù)據(jù)進行轉移。因為容量變大了，部分元素的位置因此要變更，因而出現(xiàn)了下面的這個轉移過程。

轉移過程大致是：依次從舊數(shù)組里取值，然后從該值對應的鏈表上依次取出節(jié)點，對節(jié)點取模分別放入lo鏈表和hi鏈表，當鏈表中節(jié)點遍歷完后，分別把lo鏈表和hi鏈表放入新數(shù)組的不同位置。

在看到如下第15行時，我在想，為什么（e.hash & oldCap）== 0時就放入lo鏈表，否則就是hi鏈表？

說到這個問題，那我們就要回顧下HashMap存入新元素的過程了?？聪旅娴牡?5行，可以發(fā)現(xiàn)插入時是使用(n - 1) & hash來計算位置的，即數(shù)組長度-1，而擴容移位是使用數(shù)組長度n計算的，那這是為什么呢？

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源碼，應該都應該知道HashMap的底層數(shù)組長度都是2的n方的值

那么我們就假設一個底層數(shù)組長度為8的HashMap模擬進行插入元素和擴容移位的過程

長度n=8 ----> 0x1000

n-1　　 ----> 0x0111

此時寫入兩個元素，兩個元素的hash值分別為hash2 = 0x0101，hash3 = 0x1101

hash2 & n-1 = 0x0101

hash3 & n-1 = 0x0101

兩個hash取模后的結果是一致的，所以它們會在同一個地方組成鏈表

那么此時如果要進行擴容移位呢？

hash2 & n = 0x0000

hash3 & n = 0x1000

此時兩者的結果是不一樣的，并且相差0x1000即10進制的8即數(shù)組長度.。

所以這也就是為什么上圖15行只判斷==0的原因，因為這個取模結果只有0和1兩種值（數(shù)組長度是2的n次方，只有除了符號位外的最高位為1）

而兩個取模結果等于數(shù)組長度，這也就是為什么上圖第32和36行那么處理的原因。

上述內容就是如何解析Java8 HashMap擴容算法，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

文章名稱：如何解析Java8HashMap擴容算法
文章分享：http://jinyejixie.com/article6/poeeig.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供自適應網(wǎng)站、網(wǎng)站改版、外貿建站、網(wǎng)站設計公司、網(wǎng)站內鏈、品牌網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)