【JavaSE】ArrayList的扩容机制源码分析

深碍√TFBOYSˉ_ 2024-03-27 11:18 76阅读 0赞

#### 文章目录 ####

*  1. ArrayList概述
 *  2. ArrayList构造方法源码分析
 *  3. ArrayList.add()源码分析
 *  4. ArrayList.addAll()源码分析
 *  5. 总结

## 1. ArrayList概述 ##

`ArrayList`是Java集合框架中比较常用的一个数据结构了，它底层是基于数组实现的。数组是固定大小的，但是`ArrayList`的扩容机制可以实现容量大小的动态变化。

**数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容。**

`ArrayList`的扩容是创建一个**1.5倍**的新数组，然后把原数组的值拷贝过去。

![image-20230201153601407][]

`ArrayList`添加元素有下面两种方式

1.  `public boolean add(E e)`
2.  `public boolean addAll(Collection<? extends E> c)`

下面进行源码分析

--------------------

## 2. ArrayList构造方法源码分析 ##

创建`ArrayList`集合的时候，会调用其构造方法

//存放元素的数据
    transient Object[] elementData;
    //默认空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    //集合长度
    private int size;
    
    //无参构造
    public ArrayList() {
        
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    //指定元素长度构造
    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);
        }
    }
    
    //构造参数为集合
    public ArrayList(Collection<? extends E> c) {
        
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
        
            if (c.getClass() == ArrayList.class) {
        
                elementData = a;
            } else {
        
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
        
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

1.  无参构造：无参构造会使用`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`作为存放元素的数据的数组，也就是默认集合底层的数组长度为0。
2.  指定元素长度构造：指定元素长度构造则是使用构造参数`initialCapacity`作为数组的长度。`this.elementData = new Object[initialCapacity];`
3.  构造参数为集合：使用构造参数集合`c`的长度作为底层数组`elementData`的长度，并将集合的元素拷贝成一个新数组赋值给`elementData`

--------------------

## 3. ArrayList.add()源码分析 ##

先准备一段添加数据进行的代码，添加的数据长度为15。

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

首先，创建`ArrayList`集合的时候，会调用其无参构造方法，`ArrayList`底层数组为长度为0的空数组。

下面是`add`方法的源码

public boolean add(E e) {
        
        //检查是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在添加元素进集合集合之前，需要先调用`ensureCapacityInternal`方法，检查是否要扩容。

参数为底层存储数据的数组的长度+1

private void ensureCapacityInternal(int minCapacity) {
        
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

`ensureCapacityInternal`里面`ensureExplicitCapacity`方法。

在执行`ensureExplicitCapacity`之前需要调用`calculateCapacity`方法计算需要扩容的长度。

//默认的初始化容量大小
    private static final int DEFAULT_CAPACITY = 10;
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

`calculateCapacity`方法有两个参数，`elementData`是底层用来存储数据的数组，而`minCapacity`就是新的数组长度。

在这个方法里，首先判断一下`elementData`是不是默认的空数组（也就是是否和`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`是同一个对象）\*\*，如果是，则取新数组的长度和默认的初始化容量的长度的最大值返回。\*\*也就是说，如果集合中第一次添加元素，那么默认的容量大小为10。

如果不是默认的空数组，则将`minCapacity`也就是新的数组长度返回。

//该参数是记录列表结构以被修改的次数
    protected transient int modCount = 0;
    private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

接着比较现在新数组长度`minCapacity`和底层数组长度`elementData.length`的大小

如果`minCapacity`小于等于`elementData.length`则不需要扩容。

如果`minCapacity`大于`elementData.length`则需要扩容，调用`grow(minCapacity)`方法。

参数为新数组的长度。

//数组最大容量，-8是因为有些VM会在数组中保留一些词
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    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);
    }

**这个`grow`方法就是扩容的关键所在了。**

扩容后的数组长度的关键就是这一行代码

`int newCapacity = oldCapacity + (oldCapacity >> 1);`

`(oldCapacity >> 1)`就是右移运算表示除以2

假设现在`oldCapacity`为10，其原码为1010，向右移动一位就是0101，也是5。

所以扩容后的新容量`newCapacity`就是15。

接着判断扩容后的容量`newCapacity`和新数组的容量`minCapacity`进行比较。

1.  如果小于，也就是扩容后的容量`newCapacity`还不够，那么将新数组的长度`minCapacity`赋值给`newCapacity`。

然后将扩容容量`newCapacity`和数组最大容量`MAX_ARRAY_SIZE`对比

1.  如果大于，则执行`hugeCapacity(minCapacity)`方法

//数组最大容量，-8是因为有些VM会在数组中保留一些词
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

`hugeCapacity(minCapacity)`方法判断如果最小扩展要求值小于0则抛出异常，否则进行判断最小扩展要求值`minCapacity`是否大于`MAX_ARRAY_SIZE`，如果大于则返回最大`int`值，如果不大于则返回`MAX_ARRAY_SIZE`值。

最后通过`Arrays.copyOf(elementData, newCapacity);`扩容就完成了。

--------------------

## 4. ArrayList.addAll()源码分析 ##

先准备一段测试代码。

public class TestArrayList {
        
        public static void main(String[] args) {
        
            ArrayList list = new ArrayList();
            list.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11));
        }
    }

下面是`addAll`的源码

public boolean addAll(Collection<? extends E> c) {
        
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

`addAll`主要的逻辑就是将传进来的集合转化为数组，拿到这个数组的长度。

接着对当前`ArrayList`执行检查扩容操作，然后`System.arraycopy`方法将`System.arraycopy`数组附加到`elementData`数组的`size`下标后，然后设置`size`的大小，最后根据传入的容器长度来返回添加状态。

--------------------

## 5. 总结 ##

1.  `ArrayList`扩容通常为原数组大小的1.5倍，并且`ArrayList`最大容量为`int`最大值。
2.  `addAll(Collection c)`没有元素时候，扩容为`Math.max(10, 实际元素个数)`，有元素时为`Math.max(原来容量的1.5倍，实际元素个数)`
3.  `add(Object o)`首次扩容为10，再次扩容为上次容量的1.5倍。
4.  `ArrayList(int initialCapacity)`会使用指定容量的数组
5.  `ArrayList(Collection<? extends E> c)`会使用c的大小作为数组容量

--------------------

[image-20230201153601407]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1ac0952f9bcd4f17a621a425d24f3d62.png