HashMap的resize()即扩容方法源码分析

ゝ一纸荒年。 2023-03-04 04:30 24阅读 0赞

直接上代码

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
                //将新数组扩容阈值赋值为默认负载因子0.75乘以默认初始化容量16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            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);//将树链表中的数据从旧数组移到新数组
                        else {  // preserve order //走到这里，说明链表头节点有后续节点，后面会保留原有链表的顺序进行新旧数组的数据转移
                        //旧数组的每个索引位置里的链表头节点转移到新数组后的索引位置时要重新rehash，重新计算的：根据(e.hash & oldCap) 
                        //是否等于0，分成2类：①等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的
                        //索引位置,记未低位区链表lo；②不等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的
                        //索引位置再加上旧数组长度，记为高位区链表hi
                            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) { 
                                //用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算，若(e.hash & oldCap)的结果为0，
                                //则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引
                                //下标位置与在旧数组的索引下标位置相同(处于同一条链表中的所有节点的hash值相同)
                                    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 { //用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算，若(e.hash & oldCap)的结果不为0，
                                //则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引下标位置与
                                //在(旧数组的索引下标位置+旧数组长度)相等(处于同一条链表中的所有节点的hash值相同)
                                    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;//返回处理完的新数组
        }