20220929-ArrayList扩容机制源码分析

示例代码

public class ArrayListSource {

    public static void main(String[] args) {

        ArrayList arrayList = new ArrayList();  //跳转至第一步

        for (int i = 0; i < 10; i++) {

            arrayList.add(i);  //需要进行第一次扩容，跳转至第二步

        }

        for (int i = 11; i <= 15; i++) {

            arrayList.add(i);  //需要进行第二次扩容

        }

        arrayList.add(100);  //需要进行第三次扩容

        arrayList.add(200);

        arrayList.add(300);

    }

}

代码分析

第一步：

当使用new ArrayList()创建集合时，会调用ArrayList类的无参构造器，在集合内部存在一个空的elementData数组，代码如下

private static final int DEFAULT_CAPACITY = 10;  //默认容量

...

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  //默认空数组

...

transient Object[] elementData;  //存放Object对象的数组

...

private int size;  //集合中所包含的元素，默认为0

...

protected transient int modCount = 0;

...

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  //MAX_ARRAY_SIZE = 2147483639

...

public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  //elementData初始化为{}数组，其中size=0

}

第二步：

程序进入for循环，从i=0开始，执行arrayList.add(i)方法，进入ArrayList类中

public boolean add(E e) {  //此时：e=1

        ensureCapacityInternal(size + 1);  //跳转至第三步

        elementData[size++] = e;

        return true;

}

第三步：

执行ensureCapacityInternal(size + 1)，其中size=0

private void ensureCapacityInternal(int minCapacity) {  //此时minCapacity=size+1=1，即给集合中添加1个元素，需要的最小容量是1

        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));  //跳转至第四步

}

第四步：

先执行ensureExplicitCapacity()中的嵌套函数calculateCapacity(elementData, minCapacity)

// elementData = {}

// minCapacity = 1

// DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}

// DEFAULT_CAPACITY = 10

private static int calculateCapacity(Object[] elementData, int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  //此if语句成立

            return Math.max(DEFAULT_CAPACITY, minCapacity);  //返回值为10，退出函数，跳转至第五步，

        }

        return minCapacity;

}

第五步：

执行ensureExplicitCapacity()函数

// minCapacity = 10

// modCount默认为0，然后自加1

// elementData.length = 0

private void ensureExplicitCapacity(int minCapacity) {

        modCount++;

        if (minCapacity - elementData.length > 0)  //此时if语句成立

            grow(minCapacity);  //跳转至第六步

}

第六步：

执行grow(minCapacity)

// minCapacity = 10

// MAX_ARRAY_SIZE = 2147483639

private void grow(int minCapacity) {

        int oldCapacity = elementData.length; //oldCapacity=0

        int newCapacity = oldCapacity + (oldCapacity >> 1);  //newCapacity=0+0/2=0

        if (newCapacity - minCapacity < 0)  //此if语句成立

            newCapacity = minCapacity;  //newCapacity = 10

        if (newCapacity - MAX_ARRAY_SIZE > 0)  //此if语句不成立

            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);

        //此语句执行后，elementData = {null,null,null,null,null,null,null,null,null,null}

}

第七步：

当程序执行完第六步之后，根据方法调用步骤依次返回，直至第二步的第2条程序语句

public boolean add(E e) {//此时：e=1

        ensureCapacityInternal(size + 1);

        //通过以上方法，确保集合中可以存放e对象

        elementData[size++] = e;//此时size=0，之后自加1；e=1

        //执行之后 elementData = {1,null,null,null,null,null,null,null,null,null}

        return true;

}

第八步：

在for循环中，不断执行 arrayList.add(i)方法，直到for循环结束，以上步骤介绍了ArrayList第一次默认初始化之后存放元素的步骤和扩容机制，当集合中存放的对象达到容量10时，集合需要再次进行扩容。而接下来的每次扩容的容量=原来容量*1.5，即 0 --> 10 --> 15 --> 22 --> 33...

巴特西

20220929-ArrayList扩容机制源码分析

示例代码

代码分析

最新文章

热门文章