原创

JDK1.8 HashMap源码解析(三) 扩容机制和resize源码详解

扩容机制核心方法 Node[] resize()

HashMap扩容可以分为三种情况:

  • 第一种:使用默认构造方法初始化HashMap(HashMap())。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table,并且thershold未赋值所以为0。
    此时oldCap=0, oldThr=thershold=0, 因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
    源代码部分
} else {  // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    //  默认 16 * 0.75 = 12
    newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
  • 第二种:指定初始容量的构造方法初始化HashMap(HashMap(int initialCapacity)以及HashMap(int initialCapacity, float loadFactor))。那么从下面源码可以看到初始容量会等于threshold,接着 threshold = 当前的容量(threshold)*DEFAULT_LOAD_FACTOR。此时oldCap=0, oldThr=thershold>0。
    源代码执行部分
else if (oldThr > 0) // initial capacity was placed in threshold
{
     newCap = oldThr;
} else {
  • 第三种:HashMap不是第一次扩容。如果HashMap已经扩容过的话,那么每次table的容量以及threshold量为原有的两倍。此时入参为Map测构造方法也可以出发扩容动作(HashMap(Map<? extends K, ? extends V> m)).
    源代码执行部分
if (oldCap > 0) {
      ......
}

HashMap是先插入数据再进行扩容的,但是如果是刚刚初始化容器的时候是先扩容再插入数据。
构造HashMap表时,如果不指明初始大小,默认大小为16(即Node数组大小16),如果Node[]数组中的元素达到(填充比0.75*Node.length)时,进行扩容操作,重新调整HashMap大小变为原来2倍大小。扩容很耗时。

/**
   * 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.
   *
   * @return the table
   */
  /**
   * 对table进行初始化或者扩容。
   * 如果table为null,则对table进行初始化
   * 如果对table扩容,因为每次扩容都是翻倍,与原来计算(n-1)&hash的结果相比,
   * 节点要么就在原来的位置,要么就被分配到“原位置+旧容量”这个位置。
   *
   * resize的步骤总结为:
   * 1.计算扩容后的容量,临界值。
   * 2.将hashMap的临界值修改为扩容后的临界值
   * 3.根据扩容后的容量新建数组,然后将hashMap的table的引用指向新数组。
   * 4.将旧数组的元素复制到table中。
   *
   * @return the table
   */
  final Node<K, V>[] resize() {
    //新建oldTab数组保存扩容前的数组table
    Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //默认构造器的情况下为0
    int oldThr = threshold;
    int newCap, newThr = 0;

    //如果旧表的长度不是空, 扩容肯定执行这个分支
    if (oldCap > 0) {
        //当前table容量大于最大值得时候返回当前table. 此时loadfactor很大,冲突量比较大,查询不再是O(1)
        if (oldCap >= MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return oldTab;

        // 把新表的长度设置为旧表长度的两倍,newCap=2*oldCap
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY) {
          //扩容容量为2倍,临界值为2倍
          newThr = oldThr << 1; // double threshold
        }

    // 如果旧表的长度的是0,就是说第一次初始化表
    } else if (oldThr > 0) // initial capacity was placed in threshold
    {
      //使用带有初始容量的构造器时,table容量为初始化得到的threshold
      newCap = oldThr;
    } else {               // zero initial threshold signifies using defaults
        //默认构造器下进行扩容
        newCap = DEFAULT_INITIAL_CAPACITY;
        //  默认 16 * 0.75 = 12
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    //使用带有初始容量的构造器在此处进行扩容
    if (newThr == 0) {
        //新表长度乘以加载因子
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
            (int) ft : Integer.MAX_VALUE);
    }

    //将新的临界值赋值赋值给threshold
    threshold = newThr;

    @SuppressWarnings({"rawtypes", "unchecked"})
    // 开始构造新表, 按newCap创建新的数组,初始化表中的数据
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    //新的数组赋值给table
    table = newTab;

    //扩容后,对新扩容后的table赋值,重新计算元素新的位置。 原表不是空要把原表中数据移动到新表中
    if (oldTab != null) {   // oldCap 原数组
      //遍历原来的旧表
      for (int j = 0; j < oldCap; ++j) {
        Node<K, V> e;

        //判断当前遍历下的该node是否为空,将j位置上的节点保存到e, 然后将oldTab[j]置为空。
        if ((e = oldTab[j]) != null) {
          // 为什么要置为空,有什么好处?? TODO
          oldTab[j] = null;

          ///普通节点, 位置是hash求余。 如果为null 说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
          if (e.next == null) {
            newTab[e.hash & (newCap - 1)] = e;
          } else if (e instanceof TreeNode) {
              //  树形结构修剪. 当扩容时,
              //  如果当前桶中元素结构是红黑树,并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD (默认为 6),就会把桶中的树形结构缩小或者直接还原(切分)为链表结构
            ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);

          // 如果e后边有链表,到这里表示e后面带着个单链表,需要遍历单链表,将每个结点重新计算在新表的位置,并进行搬运
          } else { // preserve order 保证顺序
              Node<K, V> loHead = null, loTail = null;
              Node<K, V> hiHead = null, hiTail = null;
              Node<K, V> next;

              /*
              这里如果判断成立,那么该元素的地址在新的数组中就不会改变。
              因为oldCap的最高位的1,在e.hash对应的位上为0,所以扩容后得到的地址是一样的,位置不会改变 ,在后面的代码的执行中会放到loHead中去,最后赋值给newTab[j];

              如果判断不成立,那么该元素的地址变为 原下标位置+oldCap,也就是lodCap最高位的1,在e.hash对应的位置上也为1,所以扩容后的地址改变了,在后面的代码中会放到hiHead中,最后赋值给newTab[j + oldCap]

              举个例子来说一下上面的两种情况:
                设:oldCap=16 二进制为:0001 0000
                   oldCap-1=15 二进制为:0000 1111
                   e1.hash=10 二进制为:0000 1010
                   e2.hash=26 二进制为:0101 1010
                e1在扩容前的位置为:e1.hash & oldCap-1  结果为:0000 1010
                e2在扩容前的位置为:e2.hash & oldCap-1  结果为:0000 1010
                结果相同,所以e1和e2在扩容前在同一个链表上,这是扩容之前的状态。

                现在扩容后,需要重新计算元素的位置,在扩容前的链表中计算地址的方式为e.hash & oldCap-1
                那么在扩容后应该也这么计算,扩容后的容量为oldCap*2=32,2^5, 二进制为:0010 0000。 所以 newCap=32,
                新的计算方式应该为
                e1.hash & newCap-1
                即:0000 1010 & 0001 1111
                结果为0000 1010与扩容前的位置完全一样。
                e2.hash & newCap-1 即:0101 1010 & 0001 1111
                结果为0001 1010,为扩容前位置+oldCap。

                而这里却没有e.hash & newCap-1 而是 e.hash & oldCap,其实这两个是等效的,都是判断倒数第五位是0,还是1。
                如果是0,则位置不变,是1则位置改变为扩容前位置+oldCap。

                再来分析下loTail, loHead这两个的执行过程(假设(e.hash & oldCap) == 0成立):
                第一次执行:
                e指向oldTab[j]所指向的node对象,即e指向该位置上链表的第一个元素.
                loTail为空,所以loHead指向与e相同的node对象(loHead = e;),然后loTail也指向了同一个node对象(loTail = e;)。
                最后,在判断条件e指向next,就是指向oldTab链表中的第二个元素

                第二次执行:
                lotail不为null,所以lotail.next指向e,这里其实是lotail指向的node对象的next指向e,
                也可以说是,loHead的next指向了e,就是指向了oldTab链表中第二个元素。此时loHead指向
                的node变成了一个长度为2的链表。然后lotail=e也就是指向了链表中第二个元素的地址。

                第三次执行:
                与第二次执行类似,loHead上的链表长度变为3,又增加了一个node,loTail指向新增的node......

                hiTail与hiHead的执行过程与以上相同。
                由此可以看出,loHead是用来保存新链表上的头元素的,loTail是用来保存尾元素的,直到遍历完链表。
                这是(e.hash & oldCap) == 0成立的时候。

                (e.hash & oldCap) == 0不成立的情况也相同,其实就是把oldCap遍历成两个新的链表,
                通过loHead和hiHead来保存链表的头结点,然后将两个头结点放到newTab[j]与newTab[j+oldCap]上面去。
              */
              do {
                //记录下一个结点
                next = e.next;

                // 新表是旧表的两倍容量,实例上就把单链表拆分为两队, e.hash&oldCap==0为偶数一队,反之为奇数一对
                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);

              //lo队不为null,放在新表原位置
              if (loTail != null) {
                //尾节点的next设置为空
                loTail.next = null;
                newTab[j] = loHead;
              }

              //hi队不为null,放在新表j+oldCap位置
              if (hiTail != null) {
                //尾节点的next设置为空
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
              }
          }
        }
      }
    }
    return newTab;
  }

总结

resize(扩容) 的上限

resize 不是无限的,当到达resize 的上限,也就是230 之后,不再扩容

resize 方法只有三种情况下调用

- 第一种 是在**首次插入元素的时候完成数组的初始化**
- 第二种 是在元素插入**完成后**判断是否需要数组扩容,如果是的话则调用
- 第三种 是在元素插入链表尾部之后,进入树化方法之后,如果不树化则进行resize

resize 的返回值

  • 第一种情况下 返回老的数组也就是没有resize 因为已经达到resize 的上限了
  • 第二种情况下 返回一个空的数组 也就是第一次调用resize方法
  • 第三种情况下 返回一个扩容后的数组 完成了数据迁移后的数组

key 的判断

  • 第一次判断是当前位置有元素的时候,如果两个key 相等则准备覆盖值
  • 第二次判断是遍历链表的时候,决定能否覆盖链表中间key 相等的值而不是链表的尾部

你觉得Hashmap 还有什么可以改进的地方吗,欢迎讨论

虽然java 源代码的山很高,如果你想跨越,至少你得有登山的勇气,这里我给出自己的一点点愚见,希望各位不吝指教

相关链接:

树形结构修剪

源码

最后,附源代码如下:

JDK1.8 HashMap源码解析

Demo: 测试链表转红黑树以及扩容

正文到此结束
广告是为了更好的提供数据服务
本文目录