ArrayList是工作中常用的集合, 基于数组实现, 可以插入空数据, 也支持随机访问.
ArrayList比较适合 get/set操作, 因为 add/remove需要移动数据, 相对来说比较消耗性能.

默认初始长度

1.默认初始长度为 10
2.底层结构为Object[] 数组

1
2
3
4
5
6
7
8
9
10
11
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 构造一个初始容量为10的空列表
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

添加方法 add()

  1. 向数组中添加元素, 流程如下
1
2
3
4
5
6
7
8
9
10
/**
 * 将指定的元素追加到此列表的末尾.
 */
public boolean add(E e) {
    // 扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 添加元素
    elementData[size++] = e;
    return true;
}

2.扩容过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

transient Object[] elementData;

// 扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容量, elementData为空 则使用默认容量 10, 指定容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
// 修改次数自增, 并且如果 新的长度-原长度>0 则使用 grow(minCapacity)方法进行扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

  1. 添加元素赋值
    1
    elementData[size++] = e;

扩容流程 grow(minCapacity)

通过扩容流程可以看出扩容过程中, 是将创建一个原数组1.5倍大小的新数组, 同时将数组元素复制到新数组, 所以一般使用中, 尽量指定数组大小, 从而避免数组的复制.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 增加容量确保能容纳 minCapacity 数量的元素
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    // 获取当前 elementData 的长度
    int oldCapacity = elementData.length;
    // 获取新的长度 为当前长度的 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:
    // 数组复制
    elementData = Arrays.copyOf(elementData, newCapacity);
}

删除 remove 方法

删除过程中使用 System.arraycopy 本地方法, 对数组进行复制, 所以 ArrayList的 新增和删除方法性能不如, LinkList, 但是 get和set方法, 则直接根据索引修改数据, 比较适合对数据进行修改的操作.

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
42
43
44
45
46
47
48
49
50
/**
 * 删除指定位置的元素, 后面的元素将前移
 */
public E remove(int index) {

    // 检查索引 否则抛出 IndexOutOfBoundsException(outOfBoundsMsg(index))
    rangeCheck(index);
    // 修改次数自增
    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 数组复制
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
/**
 * 删除指定元素
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
/**
 * System.arraycopy 方法拷贝 删除
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}