ArrayList: 基于动态数组的列表

ArrayList: 底层使用数组来存储列表的元素，例如 a[i] = element。

• 可重复且允许插入 null 值；
• 数组默认初始容量值为10，往后每次容量不足时扩容50%，实际调用 System.arraycopy() 方法实现；
• 建议预估并设置初始化容量值，可有效避免多次进行扩容带来的性能问题。

数组的优/劣势

• 优势：随机访问 get/set 元素速度最快，仅需要O(1)的时间复杂度。
• 劣势：remove/search 元素速度较慢，达到O(n)的时间复杂度。

主要成员变量

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
   
   private static final int DEFAULT_CAPACITY = 10;
   private static final Object[] EMPTY_ELEMENTDATA = {};
   transient Object[] elementData; // 非私有是为了简化嵌套类的访问，调试访问
   private int size;
   // 其余略过...
   
   // 此处存在一个细节，即初始化时 elementData 为空数组；
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }
}

add 方法及扩容剖析

使用该方法将元素添加至列表末尾，详见如下：

public boolean add(E e) {
    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) {
    // 默认初始时，将进行扩容为 DEFAULT_CAPACITY=10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 结构变更次数+1
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); // 真正进行扩容的方法
}

// 实际进行扩容的方法
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 容量增大为原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); // 底层使用 System.arraycopy() 
}

get 方法剖析

该方法可实现根据数组下标获取列表中的元素，详见如下：

public E get(int index) {
    rangeCheck(index); // 判断是否越界
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index]; // 直接根据数组下标获取元素
}

ArrayList 为什么是非线程安全的？

众所周知，ArrayList 是非线程安全的，接下来将探索 ArrayList 为什么是非线程安全的。先看看如下代码：

// 添加元素的方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e; // size++ 是出现非线程安全的地方之一
    return true;
}

其中 size++ 是非原子操作，可拆分为以下两个部分：

• n = size + 1； // 先加1
• size = n；// 再赋值

假设现在有两个线程：thread-a 和 thread-b，并出现以下执行顺序时(假设 size 初始值为1)，则会发生不正确的行为：

​ 1. thread-a：n = size + 1

​ 2. thread-b：n = size + 1；

​ 3. thread-b: size = n;

​ 4. thread-a: size = n; // 此时size并不是期望的值3，而是等于2

此时就会出现非线程安全情况，其他情况就不一一列举，留给读者探索。

线程安全的List

• Vector：方法的实现方式与 ArrayList 基本相同，底层使用 synchronized 修饰方法，降低了效率。
• Collections.synchronizedList(new ArrayList(...))：官方文档推荐方式，底层实现使用 synchronized(mutex) 方式。

ArrayList VS LinkedList

• ArrayList 基于动态数组，LinkedList 基于链表的数据结构；
• ArrayList 随机访问 set/get 速度快，LinkedList 随机访问速度较慢，需要从表头开始遍历；
• LinkedList 插入和删除操作速度快，ArrayList 插入和删除操作速度较慢；
• LinkedList 可作为队列来使用。