博文目录

---

原理

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
1

创建

// Default initial capacity.
// 未指定初始化容量时, 初始化后的默认容量
private static final int DEFAULT_CAPACITY = 10;

// ArrayList 中存储数据的数组, 在首次添加元素时, 如果 elementData=={}, elementData 将初始化为长度为 DEFAULT_CAPACITY 的数组
transient Object[] elementData; // non-private to simplify nested class access

// 创建 ArrayList 且指定了初始容量为 0 时, ArrayList 内的 elementData 被赋值为 EMPTY_ELEMENTDATA
private static final Object[] EMPTY_ELEMENTDATA = {};

//  创建 ArrayList 且未指定初始容量时, ArrayList 内的 elementData 被赋值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存储 ArrayList 中添加了的元素数量, 同时也是 ArrayList 中逻辑上的最后一个元素的索引位置
private int size;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 指定初始容量的创建方式
// 指定的容量大于0时, elementData 初始化为指定容量的 Object 数组
// 指定的容量等于0时, elementData 初始化为空数组 {}
// 指定的容量小于0时, 报错
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);
    }
}

// 未指定初始容量的创建方式
// elementData 初始化为空数组 {}
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 给定 Collection 的创建方式
// 如果 Collection 是 empty 的, 则 elementData 初始化为空数组 {}
// 如果 Collection 不是 empty 的, 则最终将 elementData 转化为同样 size 的 Object 数组
public ArrayList(Collection<? extends E> c) {
	// toArray 是 Collection 接口定义的方法, 不同的 Collection 有不同的实现, 但效果都是把 Collection 转成同类型的数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

添加元素

public boolean add(E e) {
	// 确保 ArrayList 容量足够容纳新元素, 即如果容量不够时会执行扩容操作 grow
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// 如果 ArrayList 中的 elementData 还没初始化(即还是空数组{}), 目标容量就是10或新容量中的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果目标容量超过了 elementData 的容量上限, 则需要扩容 grow
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 右移相当于除以2, 所以新容量就是就容量的1.5倍, 这是一个经验值
    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:
    // 用 newCapacity 创建一个新的 elementData 数组, 并把旧数组中的元素拷贝过来, 完成扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

创建 ArrayList 时, 如果未指定初始容量或指定初始容量为0, 则 ArrayList 内的 elementData 会被初始化为 空数组 {}

在第一次 add 元素时, 如果 elementData 是空数组 {}, 则 elementData 将被重新初始化为容量为10的新数组

在 elementData 不足以添加新元素时, elementData 将执行 grow 扩容, 容量小于等于10时, 扩容为10, 容量大于10时, 按1.5倍大小扩容

并发操作时可能出现的问题

元素覆盖, 总 size 小于预期值

多个线程同时 add, 获取到了同一个 size, 并执行 size++, 导致后面线程覆盖了前面线程的执行结果, size 总值小于预期值, 并且后面线程添加的元素覆盖了前面线程添加的元素

空元素

多个线程同时扩容, 同时获取到了旧的 elementData, 线程a先生成了新的 elementData, 并拷贝好旧元素, 并添加好新元素(size++, 假设新元素的位置是10, 执行后size变成11). 线程b这时候也生成了新的 elementData(这个数组里没有线程a添加的新元素), 并拷贝好旧元素, 接下来添加新元素的时候, 获取到的size是11, 即b将新元素放到了位置11. 最终导致丢失了a添加的新元素, 但是位置却空出来了, 即位置10变成了null, 导致出现了空元素

数组越界

在 elementData 只剩一个空位时, 多个线程并发 add, 都得到容量足够, 都执行 elementData[size++] = e;, 后执行的线程, 因为 size 索引超过了可用索引, 导致数组越界