源码剖析Java8HashMap的resize扩容时机？扩容机制？

r囧r小猫 2023-10-01 17:35 30阅读 0赞

本文从两个面试题分析HashMap的resize()方法源码，分别是：HashMap什么时候扩容？HashMap扩容做了什么？

### 1、HashMap什么时候扩容？ ###

1.  第一次添加元素时，即当HashMap的数组为null或者数组的长度为0时；  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16]
2.  链表转红黑树、且数组容量小于64时；  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 1]
3.  数组容量大于扩容阈值时；  
    ![在这里插入图片描述][ac9f5aadfc934fbc8c2f07b0313da29a.png]

### 2、HashMap扩容做了什么？ ###

这里也是resize()方法源码解析。

HashMap的resize()方法扩容大致可以分为两个阶段；

1.  第一阶段：参数newCap、newThr、threshold的解析计算；
2.  第二阶段：根据参数newCap、newThr进行rehash，构建新的数组。

**resize()方法中的局部变量解释：**  
![在这里插入图片描述][ff43c854c6b84604bc07d6cfc2ed24aa.png]

#### 1）第一阶段 ####

**第一阶段，计算newCap、newThr：**

> 1.  如果HashMap的数组中有数据，对数组进行两倍扩容；数组容量的上限为`1 << 30`；
> 2.  如果HashMap的数组中没有数据，设置数组容量为默认值16、扩容阈值为默认值12；

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 2）第二阶段 ####

**第二阶段，根据第一阶段计算出的newCap、newThr进行rehash构建新数组：**

> 如果老的数组中有数据，则进行数据迁移；数据迁移步骤如下：
> 
> 1.  遍历老数组的每个槽位；
> 2.  如果槽位中是一个普通节点，则将节点放在新数组中，所在新数组中的下标计算方式为：`e.hash & (newCap - 1)`;
> 3.  如果槽位中是一个树节点，则进行红黑树的迁移操作，新数组中下标计算方式同普通节点；
> 4.  如果槽位中是一个链表节点，则将链表拆为高位链表和低位链表，分别放入新数组的旧数组的下标位置和 （旧数组下标 + 旧数组容量）下标位置；
> 5.  最后返回新数组。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 完整流程图 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

#### 完整源码 ####

final Node<K,V>[] resize() {
        
        // 阶段一：计算newCap、newThr
        // 没插入数据之前的哈希数组oldTab
        Node<K,V>[] oldTab = table;
        // old数组的容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // old扩容阈值
        int oldThr = threshold;
        // 新的数组容量和扩容阈值
        int newCap, newThr = 0;
        // oldCap > 0表示不是首次初始化，因为hashMap用的是懒加载
        if (oldCap > 0) {
        
            // 老数组容量大于最大容量（1 << 30）时
            if (oldCap >= MAXIMUM_CAPACITY) {
        
                // 扩容阈值为整数的最大值
                threshold = Integer.MAX_VALUE;
                // 然后就不扩容了
                return oldTab;
            }
            // 两倍扩容，并且扩容后的长度要小于最大值、old容量要大于等于16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 扩容阈值变为原扩容阈值的2倍
                newThr = oldThr << 1; 
        }
    
        // 处理情况：溢出越界
        else if (oldThr > 0) 
            newCap = oldThr;
        // 新的HashMap首次初始化时，设置数组容量
        else {
                       
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 扩容阈值等于容量*加载因子
            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 = newThr;
        // 表示忽略该警告
        @SuppressWarnings({
        "rawtypes","unchecked"})
            // 初始化数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // rehash操作，
        if (oldTab != null) {
        
            for (int j = 0; j < oldCap; ++j) {
        
                // 临时变量
                Node<K,V> e;
                // 当前哈希桶的位置值不为null，也就是数组下标处有值，因为有值表示可能会发生冲突
                if ((e = oldTab[j]) != null) {
        
                    // 把已经赋值之后的变量置位null，当然是为了便于回收，释放内存
                    oldTab[j] = null;
                    // 如果下标处的节点没有下一个元素，也就是普通节点
                    if (e.next == null)
                        // 把该变量的值存入newCap中，数组下标为e.hash & (newCap - 1)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素
                    else if (e instanceof TreeNode)
                        // 把此树进行转移到newCap中
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
         
                        // 此处表示为链表结构，同样把链表转移到newCap中；
                        // 则将链表拆为高位链表和低位链表，分别放入新数组的旧数组的下标位置和 （旧数组下标 + 旧数组容量）下标位置；
                        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;
                            }
                            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;
                        }
                    }
                }
            }
        }
        //返回扩容后的hashMap
        return newTab;
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0c877b35b5c546039ebe17cfef86e9ef.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/f2ac5efb5455458080dfb251e918c53e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[ac9f5aadfc934fbc8c2f07b0313da29a.png]: https://img-blog.csdnimg.cn/ac9f5aadfc934fbc8c2f07b0313da29a.png
[ff43c854c6b84604bc07d6cfc2ed24aa.png]: https://img-blog.csdnimg.cn/ff43c854c6b84604bc07d6cfc2ed24aa.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/5214dd827104405da79ab323b586a57d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/c87943fd9ea64f9eb918cd15e8f1799d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/62537c4159594b108dee8e42db248aab.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center