当前位置：首页 > article >正文

Java集合ArrayList的扩容原理是什么？附源码讲解+举例说明

article 2024/9/30 16:44:42

1. 源码逐步讲解

public static void main(String[] args) throws Exception{
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
}

首先我们来创建一个ArrayList对象，根据源码看一看它底层做了哪些操作：

public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

那elementData又是什么呢？

transient Object[] elementData;

其实就是一个Object数组，也就是说ArrayList底层，就是一个Object数组；

接下来我们来看一下上述代码中elementData的初始值是什么呢？

private static final Object[] EMPTY_ELEMENTDATA = {};

肯定也是一个数组，但不同的是它是一个空数组；

所以当执行这一行代码的时候：

ArrayList<Integer> list = new ArrayList<>();

它只是在底层创建了一个空数组，这个数组此时的长度等于零；

这个ArrayList数组它是当你进行第一个元素添加的时候，它才会去进行内存空间的开辟，也就是说会进行第一次扩容(创建对象之后长度为0)。

接下来我们看一下这个add方法的源码：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

首先它会调用ensureCapacityInternal()方法，这个方法就是根据需要去进行扩容的，第二行代码(elementData[size++] = e;)则是给我们这个底层数组进行赋值的。

接下来我们看一下这个扩容方法：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

这里它会传递一个参数，叫做最小容量。既然你想要扩容，那你肯定得告诉我你现在需要多少容量吧。同时这里会有一个二次计算，那这个二次计数的用处是什么呢？

if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

它主要是来判断你是不是第一次添加元素。if语句中判断这个数组是不是空，前面我们提到EMPTY_ELEMENTDATA是一个空数组。如果是空的话，说明你是第一次添加，那么它就会把这个容量直接给你变成一个默认值(DEFAULT_CAPACITY)，它的值为10。

private static final int DEFAULT_CAPACITY = 10;

也就是说这个ArrayList初始容量就是10。但如果不是第一次添加元素的话，它就不会走if这个逻辑，而是直接返回你所需要的容量。我们接着往下看：当计算出容量之后，它就会调用这个方法ensureExplicitCapacity()。

ensureExplicitCapacity(minCapacity);

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

这个方法的作用呢就是它会判断你到底需不需要扩容，那这里又是根据什么判断呢？那就是根据你需要的容量和当前我们这个数组的长度来判断：如果你需要的容量大于了我们当前数组的长度，那么就说明需要扩容。反之，若小于或者等于当前数组的长度，就说明不需要扩容。进行扩容时会调用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);
}

其基本逻辑就是：会新创建一个数组，把原来数组的值复制到这个新数组里面，这样就算是扩容了。它会将我们当前数组的长度计算出来赋值到oldCapacity中，然后根据当前数组的长度去计算我们新数组的长度，然后将其赋值到newCapacity中。newCapacity计算逻辑：旧数组的长度 + (旧数组的长度 ÷ 2)。最后再通过Arrays的copyOf()方法赋值给elementData，从而实现扩容。

oldCapacity >> 1：这是一个位运算符，表示将 oldCapacity 的值右移1位，相当于除以2。

oldCapacity + (oldCapacity >> 1)：将 oldCapacity 的值加上它的一半。

2. 举例说明

比如我想从10扩容到20，这个实现逻辑是怎样的呢？

如果你的ArrayList当前容量是10，并且你想要扩容到20，那么按照ArrayList的扩容机制，它不会直接从10扩容到20，而是会按照以下步骤进行：

计算新容量：首先，ArrayList会计算新容量。根据ArrayList的扩容机制，新容量是当前容量加上当前容量的一半。所以，如果当前容量是10，那么计算公式如下：
```
int newCapacity = oldCapacity + (oldCapacity >> 1);
```
将10代入oldCapacity，计算结果是：
```
newCapacity = 10 + (10 >> 1);
newCapacity = 10 + 5;
newCapacity = 15;
```
因此，新容量计算结果是15，而不是你期望的20。
检查新容量：ArrayList会检查计算出的新容量是否满足需求。在这个例子中，新容量15不满足你的需求（20），所以它会继续扩容。
再次计算新容量：ArrayList会继续按照相同的规则计算新容量，直到新容量满足需求。但是，由于ArrayList的扩容机制是每次增加50%，所以它不会直接跳到20，而是会继续按照这个规则增加。
最终扩容：最终，ArrayList会通过连续的扩容操作，直到新容量满足或超过20。在这个过程中，可能会先扩容到15，然后再次扩容到22（15 + (15 >> 1) = 22），这样新容量就超过了20。
复制元素：一旦新容量确定，ArrayList会创建一个新的数组，并把旧数组中的所有元素复制到新数组中。
更新引用：复制完成后，ArrayList会将内部数组的引用指向新的数组。
添加新元素：最后，如果需要，你可以继续添加新元素到ArrayList中。