让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)

简介: `HashMap`的`resize()`方法主要用于数组扩容,包括初始化或加倍数组容量。该方法首先计算新的数组容量和扩容阈值,然后创建新数组。接着,旧数组中的数据根据`(e.hash & oldCap)`是否等于0被重新分配到新数组中,分为低位区和高位区两个链表,确保数据迁移时的正确性和高效性。

分析HashMap的resize()即扩容方法的源码,会发现主要分两部分操作:

  1. 为创建新数组初始化新数组容量和新数组扩容阈值;
  2. 创建新数组后,需将数据从旧数组转移到新数组上来,旧数组上的数据会根据(e.hash & oldCap) 是否等于0,重新rehash计算其在新数组上的索引位置,分成2类:
    ① 等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记未低位区链表lo开头-low;
    ② 不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度,记为高位区链表hi开头high(具体推导过程,详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导》).
    具体,详见下述的源码解析:
    /*HashMap的resize()方法/
/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
*初始化或者加倍数组长度.若未指定要扩的容量值,则按照字段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的n次幂的格式,当扩容后,数组原来的每个桶中的元素要么保存在原位置,要么相比旧数组,扩容到新数组后,位置的偏移量为2的n次幂。
     *
     * @return the table
     */
    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) {
   //如果旧数组容量>0
            if (oldCap >= MAXIMUM_CAPACITY) {
   //如果旧数组容量大于等于最大容量
                threshold = Integer.MAX_VALUE; //则直接修改旧数组扩容阈值为最大值
                return oldTab; //并返回旧数组容量,不再做其他操作
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//若旧数组容量小于最大容量且新数组容量扩大至旧数组容量的2倍后依旧小于最大容量,并且//旧数组容量大于等于默认的初始化容量16
                newThr = oldThr << 1; // double threshold //则将新数组扩容阈值扩大至旧数组扩容阈值的2倍
        }
        else if (oldThr > 0) // initial capacity was placed in threshold//若旧数组容量小于等于0,且旧数组扩容阈值大于0(当new HashMap(0)后再put时,会走到这里)
            newCap = oldThr; //则将旧数组扩容阈值赋给新数组容量
        else {
   // zero initial threshold signifies using defaults//若旧数组容量和旧数组扩容阈值均不大于0,说明数组需要初始化
            newCap = DEFAULT_INITIAL_CAPACITY; //将新数组容量设为默认初始化容量16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //将新数组扩容阈值设为默认负载因子0.75*默认初始化容量16=12
        }
        if (newThr == 0) {
   //经上述逻辑后新数组扩容阈值仍为0,说明新数组扩容阈值尚未处理过,但走到这里之前新数组容量已经被处理完了,所以需按照新数组容量*负载因子的公式重新计算
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr; //将新数组扩容阈值赋值给HashMap的扩容阈值字段
        @SuppressWarnings({
   "rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //按照新数组容量创建新数组
        table = newTab; //将创建的新数组赋值给HashMap的数组字段
        if (oldTab != null) {
   //若旧数组不为null,则需要将旧数组中的数组迁移到新数组中,并将旧数组各位置置为null.
            for (int j = 0; j < oldCap; ++j) {
   //根据旧数组长度,循环遍历各数组索引下标
              Node<K,V> e;
              if ((e = oldTab[j]) != null) {
   //判断每个数组索引位置对应的链表的头节点是否为空,若为空则该索引位置无数据,就不需要接下来的操作,不为空才继续往下进行处理,将该链表的数据转移赋值给新数组
                oldTab[j] = null; //将旧数组该位置置为null,提醒gc回收
                if (e.next == null) //头节点无后续节点,说明只需将头节点移动到新数组
                  newTab[e.hash & (newCap - 1)] = e; //根据新数组长度和该链表头节点已有的hash重新计算该链表头节点在新数组中的索引下标位置,并将头节点直接赋值给新数组的该索引下标。
                else if (e instanceof TreeNode) //判断链表头节点类型是否是红黑树
                  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //将树中的数据从旧数组移到新数组(此方法解读详见:《HashMap中红黑树TreeNode的split方法源码解读》)
                else {
    // preserve order//走到这里,说明链表头节点有后续节点,后面会保留原有链表的顺序进行新旧数组的数据转移
//旧数组的每个索引位置里的链表头节点转移到新数组后的索引位置是要重新rehash,重新计算的:根据(e.hash & oldCap) 是否等于0,分成2类:①等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记未低位区链表lo开头-low;②不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度,记为高位区链表hi开头high(具体推导过程,详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》)。
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) {
   //详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》:用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算,若(e.hash & oldCap)的结果为0,则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引下标位置与在旧数组的索引下标位置相同(处于同一条链表中的所有节点的hash值相同):(2oldCap -1) & e.hash=(oldCap -1) & e.hash.[注意:1.旧数组长度oldCap为2的n次幂;2.计算某链表节点e在长度为n的数组中的索引下标的公式为(n-1)&e.hash;3.数据e的hash是根据e的key计算得到的,公式为(h=key.hashCode()) ^ (h>>>16)].
                      if (loTail == null) //低位链表的末尾为null, 对于每个链表来说,说明是第一次走到这里,而且此处也只会走进来一次,因为后续会将非null的e赋值给loTail了。
                        loHead = e; //说明e为低位链表头节点,并将其赋给代表低位链表头节点的loHead 
                      else//说明低位链表末尾不为null,说明至少处理过一次loTail了,即头节点肯定已经处理过了,下面应该去处理低位链表头节点的后续节点了
                        loTail.next = e; //处理完低位链表头节点后,根据next=e.next和while((e=next)!=null),依次循环递进处理低位链表头节点的后续节点,将旧数组中的链表头节点的后续节点,追加到低位链表头节点loHead的next里。
                      loTail=e; //将非null的e赋给loTail,首次走到这里时,loTail和loHead都指向e。
                    }
                    else {
   //详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》: 用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算,若(e.hash & oldCap)的结果不为0,则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引下标位置与在(旧数组的索引下标位置+旧数组长度)相等(处于同一条链表中的所有节点的hash值相同):(2oldCap -1) & e.hash=(oldCap -1) & e.hash+oldCap.[注意:1.旧数组长度oldCap为2的n次幂;2.计算某链表节点e在长度为n的数组中的索引下标的公式为(n-1)&e.hash;3.数据e的hash是根据e的key计算得到的,公式为(h=key.hashCode()) ^ (h>>>16)].
                      if (hiTail == null) //高位链表的末尾为null,对于每个链表来说,说明是第一次走到这里,而且此处也只会走进来一次,因为后续会将非null的赋值给hiTail了。
                        hiHead = e; //说明e为高位链表头节点,并将其赋给代表高位链表头节点的hiTail 
                      else//说明高位链表末尾不为null,说明至少处理过一次hiTail了,即头节点肯定已经处理过了,下面应该去处理高位链表头节点的后续节点了
                        hiTail.next = e; //处理完高位链表头节点后,根据next=e.next和while((e=next)!=null),依次循环递进处理高位链表头节点的后续节点,将旧数组中的链表头节点的后续节点,追加到高位链表头节点loHead的next里。
                      hiTail=e; //将非null的e值赋给hiTail,首次走到这里时,hiTail和hiHead都指向e。
                     }
                  } while ((e = next) != null); //链表后续还有节点时,才继续处理,否则跳出循环
                  if (loTail != null) {
   //低位链表尾节点不为空,说明旧数组向低位链表的数据转移已处理完,可做进一步处理
                    loTail.next = null; //要保证低位链表尾节点的后续节点为null 
                    newTab[j] = loHead; //loHead代表了低位链表的头节点,也就代表了整条低位链表(其上已经将旧数组中j索引位置上的链表里的所有节点都转移到了该低位链表上),而从前面的处理逻辑可知,低位链表移动到新数组时的索引下标位置,与在旧数组上的索引位置相同,故直接将低位链表头节点赋给新数组的j索引下标位置即完成转移。
                  }
                  if (hiTail != null) {
   //高位链表尾节点不为空,说明旧数组向高位链表的数据转移已处理完,可做进一步处理

                    hiTail.next = null; //要保证高位链表尾节点的后续节点为null 
                    newTab[j + oldCap] = hiHead; // hiHead代表了高位链表的头节点,也就代表了整条高位链表(其上已经要移动到新数组(j+oldCap)索引位置上的所有节点都转移到了高位链表上),而从前面的处理逻辑可知,高位链表移动到新数组时的索引下标位置,与在旧数组上的索引位置相差了一个旧数组长度oldCap,故直接将高位链表头节点赋给新数组的(j+oldCap)索引下标位置即完成转移。
                  }
                }
              }
            }
        }
        return newTab; //返回处理完的新数组
    }
目录
相关文章
|
2月前
|
存储
让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。
59 5
|
2月前
|
机器学习/深度学习 算法
让星星⭐月亮告诉你,HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)
`HashMap` 的 `tableSizeFor(int cap)` 方法用于计算一个大于或等于给定容量 `cap` 的最小的 2 的幂次方值。该方法通过一系列的无符号右移和按位或运算,逐步将二进制数的高位全部置为 1,最后加 1 得到所需的 2 的幂次方值。具体步骤包括: 1. 将 `cap` 减 1,确保已经是 2 的幂次方的值直接返回。 2. 通过多次无符号右移和按位或运算,将最高位 1 后面的所有位都置为 1。 3. 最终加 1,确保返回值为 2 的幂次方。 该方法保证了 `HashMap` 的数组容量始终是 2 的幂次方,从而优化了哈希表的性能。
34 1
|
7月前
|
存储 算法 Java
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)
在阅读了上篇文章《【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)》之后,相信您对HashMap的基本原理和基础结构已经有了初步的认识。接下来,我们将进一步深入探索HashMap的源码,揭示其深层次的技术细节。通过这次解析,您将更深入地理解HashMap的工作原理,掌握其核心实现。
63 0
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)
|
2月前
|
Java
让星星⭐月亮告诉你,HashMap中保证红黑树根节点一定是对应链表头节点moveRootToFront()方法源码解读
当红黑树的根节点不是其对应链表的头节点时,通过调整指针的方式将其移动至链表头部。具体步骤包括:从链表中移除根节点,更新根节点及其前后节点的指针,确保根节点成为新的头节点,并保持链表结构的完整性。此过程在Java的`HashMap$TreeNode.moveRootToFront()`方法中实现,确保了高效的数据访问与管理。
30 2
|
2月前
|
Java 索引
让星星⭐月亮告诉你,HashMap之往红黑树添加元素-putTreeVal方法源码解读
本文详细解析了Java `HashMap` 中 `putTreeVal` 方法的源码,该方法用于在红黑树中添加元素。当数组索引位置已存在红黑树类型的元素时,会调用此方法。具体步骤包括:从根节点开始遍历红黑树,找到合适位置插入新元素,调整节点指针,保持红黑树平衡,并确保根节点是链表头节点。通过源码解析,帮助读者深入理解 `HashMap` 的内部实现机制。
35 2
|
2月前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
57 0
|
7月前
|
存储 安全 Java
HashMap源码全面解析
HashMap源码全面解析
|
2月前
|
Java 索引
让星星⭐月亮告诉你,HashMap中红黑树TreeNode的split方法源码解读
本文详细解析了Java中`HashMap`的`TreeNode`类的`split`方法,该方法主要用于在`HashMap`扩容时将红黑树节点从旧数组迁移到新数组,并根据`(e.hash & oldCap)`的结果将节点分为低位和高位两个子树。低位子树如果元素数少于等于6,则进行去树化操作;若多于6且高位子树非空,则进行树化操作,确保数据结构的高效性。文中还介绍了`untreeify`和`replacementNode`方法,分别用于将红黑树节点转换为普通链表节点。
26 2
|
2月前
|
存储 Java
HashMap之链表转红黑树(树化 )-treefyBin方法源码解读(所有涉及到的方法均有详细解读,欢迎指正)
本文详细解析了Java HashMap中链表转红黑树的机制,包括树化条件(链表长度达8且数组长度≥64)及转换流程,确保高效处理大量数据。
96 1
|
2月前
|
存储 缓存 Java
HashMap源码解析
HashMap源码解析