HashMap的尾部遍历问题 （Tail Traversing）

• 2020 年 2 月 24 日
• 筆記

JDK1.7的HashMap在实现resize()时，新table[]的列表采用LIFO方式，即队头插入。 这样做的目的是：避免尾部遍历。

避免尾部遍历是为了避免在新列表插入数据时，遍历到队尾的位置。因为，直接插入的效率更高。

对resize()的设计来说，本来就是要创建一个新的table，列表的顺序不是很重要。但如果要确保插入队尾，还得遍历出链表的队尾位置，然后插入，是一种多余的损耗。 直接采用队头插入，会使得链表数据倒序。

例如原来顺序是：

 10  20  30  40

插入顺序如下

   10     20  10     30 20 10     40 30 20 10

存在问题：

采用队头插入的方式，导致了HashMap在“多线程环境下”的死循环问题：http://www.cnblogs.com/chengdabelief/p/7419776.html

JDK1.8的优化

JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，JDK1.8不会倒置，通过增加tail指针，既避免了死循环问题（让数据直接插入到队尾），又避免了尾部遍历。代码如下：

final Node<K,V>[] resize() {      Node<K,V>[] oldTab = table;      int oldCap = (oldTab == null) ? 0 : oldTab.length;      int oldThr = threshold;      int newCap, newThr = 0;      if (oldCap > 0) {          // 超过最大值就不再扩充了，就只好随你碰撞去吧          if (oldCap >= MAXIMUM_CAPACITY) {              threshold = Integer.MAX_VALUE;              return oldTab;          }          // 没超过最大值，就扩充为原来的2倍          else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                   oldCap >= DEFAULT_INITIAL_CAPACITY)              newThr = oldThr << 1; // double threshold      }      else if (oldThr > 0) // initial capacity was placed in threshold          newCap = oldThr;      else {               // zero initial threshold signifies using defaults          newCap = DEFAULT_INITIAL_CAPACITY;          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);      }      // 计算新的resize上限      if (newThr == 0) {            float ft = (float)newCap * loadFactor;          newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                    (int)ft : Integer.MAX_VALUE);      }      threshold = newThr;      @SuppressWarnings({"rawtypes","unchecked"})          Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];      table = newTab;      if (oldTab != null) {          // 把每个bucket都移动到新的buckets中          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;                          }                          // 原索引+oldCap                          else {                              if (hiTail == null)                                  hiHead = e;                              else                                  hiTail.next = e;                              hiTail = e;                          }                      } while ((e = next) != null);                      // 原索引放到bucket里                      if (loTail != null) {                          loTail.next = null;                          newTab[j] = loHead;                      }                      // 原索引+oldCap放到bucket里                      if (hiTail != null) {                          hiTail.next = null;                          newTab[j + oldCap] = hiHead;                      }                  }              }          }      }      return newTab;  }