JAVA基础集合框架【四】HashMap之源码分析扩容机制

文章首发于：clawhub.club

---

为什么要有扩容：

• 随着HashMap中元素的数量增长，计算hash发生碰撞的概率也就越来越大，所产生的链表长度越来越长，这样也就影响到HashMap的性能。
• 为了保证HashMap的效率，要增加HashMap长度，以减少桶内节点太多。即在某个临界点进行扩容处理。
  进行扩容，会发生一次重新hash分配，而且会遍历hash表中所有的元素，这是是非常耗时的。在编写程序中，要尽量避免resize。
• 如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。

临界点选择：

当 HashMap 中的 size >= threshold 时，HashMap 就要扩容。

• size：HashMap表中包含的键值映射的数目。
• threshold：要调整大小的下一个大小的阈值，等于(capacity * loadFactor)。
• capacity：HashMap容量
• loadFactor：哈希表的加载因子。

源码分析：

/**
    * Initializes or doubles table size.  If null, allocates in
    * accord with initial capacity target held in field threshold.
    * Otherwise, because we are using power-of-two expansion, the
    * elements from each bin must either stay at same index, or move
    * with a power of two offset in the new table.
    *
    * 初始化或两倍表大小。如果为空，则按照字段阈值中包含的初始容量目标分配。
    * 否则，因为我们使用的是2的幂展开，所以每个桶中的元素必须保持相同的索引，或者在新表中以2的幂偏移量移动。
    * @return the table
    */
   final Node<K, V>[] resize() {
       //老的表，有可能为null
       Node<K, V>[] oldTab = table;
       //获取老的表的长度
       int oldCap = (oldTab == null) ? 0 : oldTab.length;
       //老的扩容阈值
       int oldThr = threshold;
       //新的表长度，扩容阈值
       int newCap, newThr = 0;
       // 老的表长度大于0
       if (oldCap > 0) {
           // 最大的时候，不管理，直接返回
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
               // 新的表长度变为以前老表长度的2倍
               newThr = oldThr << 1; // double threshold
       } else if (oldThr > 0) // initial capacity was placed in threshold
           //如果老的阈值大于0，且老的表长度为0，则新表容量设置为老阈值
           newCap = oldThr;
       else {               // zero initial threshold signifies using defaults
           //初始阈值为零表示使用默认值：16
           newCap = DEFAULT_INITIAL_CAPACITY;
           //扩容阈值：16*0.75
           newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
       //如果新的阈值为0，则根据新的表容量计算出。
       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) {
           //迭代老的表
           for (int j = 0; j < oldCap; ++j) {
               Node<K, V> e;
               //如果表中桶内容不为null
               if ((e = oldTab[j]) != null) {
                   //清空，help GC
                   oldTab[j] = null;
                   //如果桶中不存在下一个节点
                   if (e.next == null)
                       //将此桶计算hash,重新放入新桶中
                       newTab[e.hash & (newCap - 1)] = e;
                   //如果桶中元素为树形节点
                   else if (e instanceof TreeNode)
                       // 将树仓中的节点拆分为上下树仓，如果太小，则取消树仓。仅从resize调用;
                       // 红黑树这后面专门分析
                       ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                   else { // preserve order
                       //是链表结构，且后面有节点，进行链表复制
                       //它并没有重新计算元素在数组中的位置
                       //而是采用了原始位置加原数组长度的方法计算得到位置


                       //位置没有变化的，放到lo
                       Node<K, V> loHead = null, loTail = null;

                       //位置发生变化的，当到hi
                       Node<K, V> hiHead = null, hiTail = null;
                       //下一个节点
                       Node<K, V> next;
                       do {
                           //下一个节点
                           next = e.next;
                           // (e.hash & oldCap) 得到的是 元素的在数组中的位置是否需要移动,示例如下
                           // 示例1：
                           // e.hash=10 0000 1010
                           // oldCap=16 0001 0000
                           //	 &   =0	 0000 0000       比较高位的第一位 0
                           //结论：元素位置在扩容后数组中的位置没有发生改变

                           // 示例2：
                           // e.hash=17 0001 0001
                           // oldCap=16 0001 0000
                           //	 &   =1	 0001 0000      比较高位的第一位   1

                           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;
                       }
                   }
               }
           }
       }
       return newTab;
   }

结论：

HashMap使用resize()方法来进行扩容，计算table数组的新容量和Node在新数组中的新位置，将旧数组中的值复制到新数组中，从而实现自动扩容。

• 1、当空的HashMap实例添加元素时，会以默认容量16为table数组的长度扩容，此时 threshold = 16 * 0.75 = 12。
• 2、当不为空的HashMap实例添加新元素数组容量不够时，会以旧容量的2倍进行扩容，当然扩容也是大小限制的，扩容后的新容量要小于等于规定的最大容量，使用新容量创建新table数组，然后就是数组元素Node的复制了，计算Node位置的方法是 index = (n-1) & hash，这样计算的好处是，Node在新数组中的位置要么保持不变，要么是原来位置加上旧数组的容量值，在新数组中的位置都是可以预期的（有规律的），并且链表上Node的顺序也不会发生改变。