526互联

Java - ArrayList 扩容原理和线程不安全

发布时间 2023-11-06 17:54:35作者: Himmelbleu

基础知识

ArrayList 内部维护一个数组，这个数组是一个 Object 类型的数组，可以存储任何类型的对象。当你向 ArrayList 中添加元素时，元素被存储在这个数组中。

当添加元素时，它会检查当前元素数量是否已经达到了内部数组的容量限制。如果达到了限制，ArrayList 会创建一个新的数组，通常是当前容量的 1.5 倍（具体增长因实现而异），然后将现有元素从旧数组复制到新数组。

ArrayList 在插入和删除元素方面的性能比较差。如果你在中间位置插入或删除元素，需要将后续元素向后或向前移动，以维护连续的元素存储。这些操作的时间复杂度是线性的（O(n)），其中 n 是数组中的元素数量。

分析扩容步骤

file:[Main.java]
public class Main {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println(list);
    }

}

如上所示，new 一个 ArrayList，调用无参构造函数，创建一个空的数组，数组长度为 0：

file:[ArrayList.java]
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

后续调用了 4 次 add 方法，往 ArrayList 中添加元素。添加时会涉及到四个方法：

file:[ArrayList.java]
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)];
    }
}

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

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

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

依次从下往上的顺序调用这四个方法，首先检查当前 size ArrayList 的长度是否等于真实存储数据的数组（elementData）长度一致，如果长度一致就说明数组已经达到了最大容量，就需要调用 grow() 方法进行扩容。

tip:[start]

elementData 是 ArrayList 内部维护的真实存储数据的数组，其类型为 Object。

tip:[end]

如果是初始化之后添加元素，会走 else 分支，为其创建一个长度为 10 的数组，数组长度由常量 DEFAULT_CAPACITY 指定。然后让 elementData 指向一个新的数组。此时的 elementData 已经是一个长度为 10 的数组了，然后回到 add(E e, Object[] elementData, int s) 方法，在数组的最后一个位置上面添加元素，此时的数组长度 size = s + 1;，自加 1。

否则，就走 if 分支，计算对 elementData 数组扩容多长，然后调用 Arrays.copyOf 把以前数组里面的内容复制到新的数组里，并让 elementData 指向一个新的数组。

tip:[start]

建议复制代码到 Idea 进行调试查看初始化和扩容的步骤。给 new、和 add 这些地方添加上断点，然后按 Ctrl+F5 进行调试。

tip:[end]

线程不安全

ArrayList 是一个线程不安全的集合，也就是说在多线程、并发的业务场景下，操作 ArrayList 是不安全的，会有数据不一致的情况。线程安全的 List 实现类是 Vector，它们很相似，但是是线程安全的。

如果非要用 ArrayList，可以通过 Collections.synchronizedList(new ArrayList()) 创建它。

file:[Main.java]

public class Main {

    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        final List<Integer> synchronizedList = Collections.synchronizedList(arrayList);

        Runnable addTask = () -> {
            for (int i = 0; i < 1000; i++) {
                synchronizedList.add(i);
            }
        };

        Runnable removeTask = () -> {
            for (int i = 0; i < 1000; i++) {
                if (!synchronizedList.isEmpty()) {
                    synchronizedList.remove(synchronizedList.size() - 1);
                }
            }
        };

        Thread thread1 = new Thread(addTask);
        Thread thread2 = new Thread(removeTask);

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.fillInStackTrace();
        }

        System.out.println("ArrayList size: " + synchronizedList.size());
    }

}

通过线程安全的创建 ArrayList，在多线程的情况下，不会抛出异常，并且数据也是一致性的。