ArrayList 集合底层原理

查看 ArrayList 源码

在 IDEA 中按下 Ctrl + N, 搜索 ArrayList

打开 ArrayList 源码, 按下 Alt + 7 查看 ArrayList 的 Structure

成员变量

我们主要关注以下两个成员变量

transient Object[] elementData; 

private int size;

成员变量 elementData 是一个数组, 用于存储 ArrayList 里面的元素, transient 标记该变量不应被序列化

size 存储了当前 ArrayList 中的元素数量, 同时标记了下次在 elementData 数组中添加元素的位置索引

空参构造方法

首先找到 ArrayList 的空参构造方法 ArrayList()

public ArrayList() {  
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

空参构造方法将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData, 即首先创建了一个空数组

添加单个元素

public boolean add(E e) {  
    modCount++;  
    add(e, elementData, size);  
    return true;  
}

add(E e) 方法调用了 add(E e, Object[] elementData, int s) 方法

private void add(E e, Object[] elementData, int s) {  
    if (s == elementData.length)  
        elementData = grow();  
    elementData[s] = e;  
    size = s + 1;  
}

add(E e, Object[] elementData, int s) 方法首先判断当前 ArrayList 的 size 是否等于 elementData.length 的长度, 即 elementData 数组是否已经存满

如果 elementData 数组已经存满, 则调用 grow() 方法对数组进行扩容

private Object[] grow() {  
    return grow(size + 1);  
}

grow() 方法调用 grow(int minCapacity) 方法, 并将 size + 1 作为当前所需的最小容量传入

private Object[] grow(int minCapacity) {  
    int oldCapacity = elementData.length;  
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
        int newCapacity = ArraysSupport.newLength(oldCapacity,  
                minCapacity - oldCapacity, /* minimum growth */  
                oldCapacity >> 1           /* preferred growth */);  
        return elementData = Arrays.copyOf(elementData, newCapacity);  
    } else {  
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];  
    }  
}

该方法首先记录当前的 elementData 数组长度, 即老容量

添加第一个元素

当添加第一个元素时, oldCapacity 等于 0, 所以执行

return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]

创建一个新数组, 大小为 Math.max(DEFAULT_CAPACITY, minCapacity)

而 DEFAULT_CAPACITY = 10, minCapacity 此时值为 1

private static final int DEFAULT_CAPACITY = 10;

所以添加第一个元素后, 数组扩容为 10

添加后续元素

当添加后续元素出现容量不够时, 会执行

int newCapacity = ArraysSupport.newLength(oldCapacity,  
                minCapacity - oldCapacity, /* minimum growth */  
                oldCapacity >> 1           /* preferred growth */);  
return elementData = Arrays.copyOf(elementData, newCapacity);  

首先调用 ArraysSupport.newLength(int oldLength, int minGrowth, int prefGrowth) 方法计算新的数组长度

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {  
    // preconditions not checked because of inlining  
    // assert oldLength >= 0    // assert minGrowth > 0  
    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow  
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {  
        return prefLength;  
    } else {  
        // put code cold in a separate method  
        return hugeLength(oldLength, minGrowth);  
    }  
}

新的数组长度为 oldLength 即 oldCapacity 加上 Math.max(minGrowth, prefGrowth)

minGrowth = minCapacity - oldCapacity, 添加单个元素时即为 1

prefGrowth = oldCapacity >> 1, 即原来容量的一半

一般来说添加单个元素的情况下 prefGrowth 都要大于 minGrowth, 所以新数组的长度为原来容量的 1.5 倍

所以添加单个元素时容量不够会扩充为原来容量的 1.5 倍

批量添加元素

调用 addAll 方法批量添加元素时, 如果数组容量不够, 同样会使用 grow() 方法扩容

public boolean addAll(Collection<? extends E> c) {  
    Object[] a = c.toArray();  
    modCount++;  
    int numNew = a.length;  
    if (numNew == 0)  
        return false;  
    Object[] elementData;  
    final int s;  
    if (numNew > (elementData = this.elementData).length - (s = size))  
        elementData = grow(s + numNew);  
    System.arraycopy(a, 0, elementData, s, numNew);  
    size = s + numNew;  
    return true;  
}

此时传入的参数是 size + numNew, numNew 即使要批量添加的元素数量

此时当计算新容量执行到 int prefLength = oldLength + Math.max(minGrowth, prefGrowth); 时, minGrowth 即为 numNew 是可能大于 prefGrowth, 即出现扩容 1.5 倍后容量仍然不够的情况

此时 prefLength = oldLength + numNew, 即新容量等于原来容量加上要添加元素的数量

总结

1.利用空参构造器创建的 ArrayList, 在底层会创建一个默认长度为 0 的数组 elementData 和一个成员变量 size 用于记录元素个数和下一次存储元素的位置

2.添加第一个元素时, 底层会创建一个新的长度为 10 的数组 elementData, size ++

3.当添加单个元素容量不够时, 会扩容到原来容量的 1.5 倍

4.当批量添加元素时, 如果扩容到原来容量的 1.5 倍还放不下, 则新容量等于原来容量加上要添加元素的数量

Sun Blog