ArrayList

一个可自动扩容的对象数组

new

默认情况下数组为一个空数组，你通过无参构造新建

1
2
3
4
5
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

当然也可以指定数组初始化大小，你传入的容量大小，如果为0则用ArrayList自带的，否则new 一个Object[你传入的容量大小]的对象数组

1
2
3
4
5
6
7
8
9
10
11
12
private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) { // 传入的的大小 > 0，则用你传入的大小
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {// 如果为为0的话，就用ArrayList自带的一个空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else { // 其他则抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

resize

ArrayList的添加并不是线程安全的，每一次添加都会size + 1用来去判定是否容量已经超过数组的容量了，如果超过了则扩容。没有则直接添加数据，最终返回true

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

ensureCapacityInternal 判定数组容量中，会去先计算容量大小，如果这个容量大于当前数组容量的长度则进行扩容。前面new的一个空ArrayList在第一个添加数组时就会在这里进行初始化成一个容量大小为10的数组对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void ensureCapacityInternal(int minCapacity) { // 这个 minCapacity 是当前数组容量 size + 1 后的值
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判断当前数组对象是否是ArrayList默认的对象数组，如果是，则将默认数组容量大小 10 与现在当前数组 size + 1 进行比较，最终返回较大的数；如果不是则直接返回 size + 1
        return Math.max(DEFAULT_CAPACITY, minCapacity); 
    }
    return minCapacity;
}

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0) // 判定最小容量，是否超过数组的长度 （第一次 10 - 0 > 0 进行扩容，否则直接跳过）
        grow(minCapacity);
}

overflows[扩容溢出问题]

对于计算机中的溢出数字看起来像一个圆环，对于一个数字溢出的数字一直 + 的话，最终会变成一个正数->溢出->正数…..

image-20230808121910960

image-20230808122302140

grow

调用grow容量进行扩容，其中容量扩容是旧容量的1.5倍，如果新的容量大小还比旧的容量大小的话，那么就用旧的容量大小，比如第一次初始化 minCapacity 为 10，但是 newCapacity 为 0 ,就产生了这种情况，然后是对溢出的判定，假如 minCapacity 已经是 Integer.MAX_VALUE + 1 此时已经溢出了，然后去减去 MAX_ARRAY_SIZE，如果按照正常数学算数 负数 - 一个数 = 负数，但是计算机中对于这种溢出的相减不一样，这里会是一个不为负数的数。hugeCapacity 方法判定要么抛出OOM，要么返回Integer的最大值，最终进行数组复制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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); // 新的容量大小等于（旧的容量大小 + 旧的容量大小 / 2）或者就是（ 1.5倍 旧容量大小）
    if (newCapacity - minCapacity < 0) // 新容量还比就容量小，就还是用旧的 （什么情况下能进入呢？第一次扩容会出现，我的minCapacity == 10, 但是newCapacity = oldCapacity + (oldCapacity >> 1) 算出来是等于 0 的于是就出现了旧容量比容量大的情况）
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新容量比 MAX_ARRAY_SIZE（）还要大的话，进行再次容量变更，此时有可能已经溢出了
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity); // 开始复制旧数组到一个新容量的数组上，最后将新数组赋值给 elementData
}

// 大容量判定赋值
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 如果容量都为负数了，则表示overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? // 如果都超过 MAX_ARRAY_SIZE（ Integer.MAX_VALUE - 8）了，就直接返回 Integer 的最大值
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E get(int index) {
   	// 判定index是否大于等于list长度
    rangeCheck(index);
	// 返回数据
    return elementData(index);
}

private void rangeCheck(int index) {
    // 大于抛下标越界异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
	// 返回elementData的index下标的数据
    return (E) elementData[index];
}

remove

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
51
52
53
54
55
56
57
58
59
// 通过下标移出数据
public E remove(int index) {
    // 上面get中的rangeCheck方法，判定传入的index是否越界
    rangeCheck(index);
	// 修改次数++
    modCount++;
    // 下标为index的值，先保存，remove掉后再返回
    E oldValue = elementData(index);
	// 算出需要移动的元素个数
	// index 后面的数向前移动
    // 1 2 3 4 5 （移出下标为2的数字3，此时4和5需要向前移动）5 - 2 - 1 = 2
    // 1 2 4 5
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 复制后面的数据
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 末尾设置为null
    elementData[--size] = null; // clear to let GC do its work 设置null，以便gc回收
	// 返回旧数据
    return oldValue;
}

// 通过传入数据
public boolean remove(Object o) {
    // 如果传入null，会去elementData数组里面去找是否有null的，会将所有null给清除掉
    if (o == null) {
        // 遍历elementData
        for (int index = 0; index < size; index++)
            // 是否找到null
            if (elementData[index] == null) {
                // 快速移出 null，并将数据前移
                fastRemove(index);
                return true;
            }
    } else {
        // 遍历elementData
        for (int index = 0; index < size; index++)
            // 是否找到o
            if (o.equals(elementData[index])) {
                // 快速移出
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    // 求出index后的数据个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // index后的数据前移
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 末尾设置为null，方便gc
    elementData[--size] = null; // clear to let GC do its work
}

clone

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 重写了clone方法
public Object clone() {
    try {
        // 调用父类Object的clone
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 复制原elementData的数据
        // 并且挂载到v上
        v.elementData = Arrays.copyOf(elementData, size);
        // 初始化modCount
        v.modCount = 0;
        // 返回
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

size

1
2
3
4
public int size() {
    // size
    return size;
}

contains

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean contains(Object o) {
    // 如果返回为-1表示为包含，否则包含
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // 添加if else 判定可以防止下面空指针异常
   	// 两个都是for循环到结尾，对于null用==来判定，对于非null用equals来判定
    // 只会返回找到的第一个
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

toArray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 返回一个复制的数组
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

// 传入一个数组，用来装elementData
public <T> T[] toArray(T[] a) {
    // 如果传入的数组长度小于 elementData 的长度
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
	   // 返回一个新的数组 
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // 将elementData 装进a里
    System.arraycopy(elementData, 0, a, 0, size);
    // a 末尾设置null，用于标记，表名此处为一个分界点，防止拿到一些原数组的数据，让复制的数据更加安全
    if (a.length > size)
        a[size] = null;
    return a;
}

clear

1
2
3
4
5
6
7
8
9
10
public void clear() {
    modCount++;

    // clear to let GC do its work
    // 全部设置成null，让gc回收
    for (int i = 0; i < size; i++)
        elementData[i] = null;
	// 重置size
    size = 0;
}

addAll

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
// 将传入的集合
// 追加数据
public boolean addAll(Collection<? extends E> c) {
    // 转成对象数组
    Object[] a = c.toArray();
    // 保存a长度
    int numNew = a.length;
    // 是否需要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将数组复制追加到elementData尾部
    System.arraycopy(a, 0, elementData, size, numNew);
    // 更新size
    size += numNew;
    // 传入集合长度不为0表示成功
    return numNew != 0;
}

// 插入数据
// 有下标的，将index下表开始移动到index + 集合的长度(将index开始的数据向后移动, 留出来的空间用来插入传入的集合数据)
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    // 是否扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        // 将原index开始的数据向后移动,从index + numNew开始
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
	// 插入新数据
    System.arraycopy(a, 0, elementData, index, numNew);
    // 更新size
    size += numNew;
 	// 返回是否添加成功
    return numNew != 0;
}

removeAll

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
51
52
// 批量remove, 删除传入的集合
public boolean removeAll(Collection<?> c) {
    // 非空判定
    Objects.requireNonNull(c);
	// false 表示 c 是否包含elementData[n] == false (0 < n < size)
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    // 临时elementData
    final Object[] elementData = this.elementData;
    // 初始化两个下标
    int r = 0, w = 0;
    // 是否修改过
    boolean modified = false;
    try {
        // 遍历elementData
        for (; r < size; r++)
            // 利用传入集合c，来判定是否elementData中的数据
            // complement == false 表示只保留c中没有的，移出c中有的
            // complement == true 表示只保留c中有的，移出c中没有的
            if (c.contains(elementData[r]) == complement)
                // 通过遍历elementData，然后将需要保留的数据再次存入到elementData中，但是可能会遗留一些数据
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 防止抛异常，导致数据不一致
        // r != size 表示没有遍历完elementData
        if (r != size) {
            // r 异常发生下标，将r及r后的数据追加到w后，后面那些数据是没有进行判定的
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            // 更新w
            w += size - r;
        }
        // 从w开始，进行清理数据(将数据设置成null)
        if (w != size) {
            // clear to let GC do its work
            // 遍历
            for (int i = w; i < size; i++)
                // 数据设置成null
                elementData[i] = null;
            modCount += size - w;
            size = w;
            // remove成功
            modified = true;
        }
    }
    return modified;
}

retainAll

1
2
3
4
5
6
7
// 批量remove，保留传入的集合
public boolean removeAll(Collection<?> c) {
    // 非空判定
    Objects.requireNonNull(c);
    // 与上面类似，但是complement是false
    return batchRemove(c, false);
}

subList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    // 返回一个 SubList对象，操作这个对象会对原elementData产生影响
    return new SubList(this, 0, fromIndex, toIndex);
}

// 通过传入下标来限制数据范围
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
    ...
}

forEach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void forEach(Consumer<? super E> action) {
	// 非空判定
    Objects.requireNonNull(action);
    // 保存修改次数
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    // 临时保存
    final E[] elementData = (E[]) this.elementData;
    // 临时size
    final int size = this.size;
    // 遍历，如果有其他线程修改，会抛出并发修改异常
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        // 调用Consumer的accept方法
        action.accept(elementData[i]);
    }
    // 修改次数不一致，抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

removeIf

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
51
52
53
54
55
56
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    // 通过BitSet来记录需要移出数据的下标
    final BitSet removeSet = new BitSet(size);
    // 修改次数
    final int expectedModCount = modCount;
    // 原elementData容量大小
    final int size = this.size;
	// 开始遍历，modCount == expectedModCount 防止并发修改
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
    	// 是否满足test
        if (filter.test(element)) {
            // 保存移出下标
            removeSet.set(i);
            removeCount++;
        }
    }
    // 是否被修改过
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    // 判定是否被修改过
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        // 新size大小
        final int newSize = size - removeCount;
        // 遍历
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            // 获取下标
            i = removeSet.nextClearBit(i);
            // 覆盖数据
            elementData[j] = elementData[i];
        }
        // 清除多余的数据
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        // 重新设置size
        this.size = newSize;
        // 判定修改异常
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

replaceAll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 替换所有数据
public void replaceAll(UnaryOperator<E> operator) {
    // 非空判定
    Objects.requireNonNull(operator);
    // 临时变量 修改次数
    final int expectedModCount = modCount;
    // 临时变量 size
    final int size = this.size;
    // 遍历 + 修改，对原来数据进行加工
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        elementData[i] = operator.apply((E) elementData[i]);
    }
    // 修改次数不一致，抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

sort

1
2
3
4
5
6
7
8
9
10
11
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    // 排序（合并排序TimSort）
    Arrays.sort((E[]) elementData, 0, size, c);
    // 防止排序中被其他线程修改
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

trimToSize

1
2
3
4
5
6
7
8
9
10
11
12
13
// 对elementData进行瘦身
public void trimToSize() {
    modCount++;
    // size < elementData的length
    if (size < elementData.length) {
        // size 是否为0，对elementData 是赋值空对象数组 EMPTY_ELEMENTDATA,还是再复制一份size 大小的 elementData
        elementData = (size == 0)
            // 空对象数组
            ? EMPTY_ELEMENTDATA
            // 赋值一份elementData的数据
            : Arrays.copyOf(elementData, size);
    }
}