快捷導(dǎo)航

Java8 HashMap擴容算法實例解析

更新時間：2019年12月24日 14:31:22 作者：枯木fc

這篇文章主要介紹了Java8 HashMap擴容算法實例解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

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

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

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

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

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

說到這個問題，那我們就要回顧下HashMap存入新元素的過程了。看下面的第45行，可以發(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源碼，應(yīng)該都應(yīng)該知道HashMap的底層數(shù)組長度都是2的n方的值

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

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

n-1　　 ----> 0x0111

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

hash1 & n-1 = 0x0101

hash2 & n-1 = 0x0101

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

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

hash1 & n = 0x0000

hash2 & n = 0x1000

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