【Java集合】ArrayList类扩容机制底层源码分析

2023-02-25 08:53:53

1.运行环境

Windows10系统、IDEA社区版、JDK8

2.调试说明

本次源码分是用IDEA的Debug功能，可一层一层的观察方法的具体实现

2.1 测试代码

实现无参构造的测试代码：

import java.util.ArrayList;
import java.util.List;

class Main{
    public static void main(String[] args) {
        List<Integer> lst= new ArrayList<>();
        for(int i = 0; i < 15; ++i) lst.add(i);
    }
}

2.2 设置断点

在构造函数一行设置断点

2.3 DeBug

开始DeBug

点击 Debug后的界面如下图所示

查看下一步跳转

3. 执行过程

3.1 流程图

带参构造

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

3.2 具体分析

执行一次add会调用的方法

add —— 确定扩容、执行赋值

ensureCapacityInernal ——调用扩容方法，记录操作数、判断是否扩容

calculateCapacity —— 计算扩容量，无参构造下，容量从10开始

ensureExpliciCapacity——记录操作计数，若容量不够则进行扩容

grow——扩容操作 ( 容量足够时不会调用）

其中比较重要的grow扩容操作它用到了一定的算法思想，接下来是分析过程

grow源代码

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

该方法首先计算新的容量newCapacity，结果为原先的1.5倍，其中运用了位运算，首先加一次原先的容量，再加上原来的容量数二进制串右移一位的值，即原先的一半，这样就相当于原先的1.5倍（向下取整）

码农公寓