Java集合-List篇

在Java集合框架中，List接口提供了多种实现类，如Vector、ArrayList和LinkedList，每种实现类都有其特定的特点和适用场景。Vector是线程安全的动态数组，适用于多线程环境；ArrayList是线程不安全的动态数组，适用于单线程环境，性能较高；LinkedList是双向链表，适用于频繁插入和删除元素的场景。ArrayList在多线程环境下存在数据不一致的问题，可以通过Collections.synchronizedList()、CopyOnWriteArrayList或手动同步来实现线程安全。CopyOnWriteArrayList通过写时复制机制和ReentrantLock保证线程安全，适用于读多写少的场景。理解这些集合类型的特点和实现原理，有助于在实际编程中选择合适的集合类型，提高代码的效率和可维护性。

List的实现

List接口是Java中常用的集合接口之一，提供了多种实现类，以满足不同的需求。以下是List接口的三个主要实现类及其特点和适用场景。

1. Vector

Vector是一个线程安全的动态数组，实现了List接口。Vector的所有方法都是同步的，因此适用于多线程环境。

特点

  • 线程安全：所有方法都使用synchronized关键字进行同步。
  • 动态调整大小：可以根据需要动态调整大小。
  • 存储结构：存储的是对象数组，当空间不足时会创建一个新的数组，并将原来的数组拷贝过去。
  • 性能较低：由于同步机制，Vector的性能通常低于非线程安全的ArrayList。

适用场景

  • 需要线程安全的场景。
  • 对性能要求不高的场景。

2. ArrayList

ArrayList是一个线程不安全的动态数组，实现了List接口。ArrayList在性能上比Vector快很多，适用于单线程环境。

特点

  • 线程不安全：没有同步机制，性能较高。
  • 动态调整大小：可以根据需要动态调整大小。
  • 存储结构：存储的是对象数组，当空间不足时会创建一个新的数组，并将原来的数组拷贝过去。
  • 扩容机制：扩容时增加50%的容量。

适用场景

  • 单线程环境。
  • 对性能要求较高的场景。

3. LinkedList

LinkedList是一个双向链表，实现了List接口。LinkedList也是线程不安全的，适用于需要频繁插入和删除元素的场景。

特点

  • 线程不安全：没有同步机制，性能较高。
  • 存储结构：使用链表结构，插入和删除元素效率高。
  • 随机访问较慢：由于不是顺序存储，访问元素时需要遍历链表，效率较低。

适用场景

  • 需要频繁插入和删除元素的场景。
  • 对随机访问性能要求不高的场景。

示例代码

1
2
3
4
5
6
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
for (String element : linkedList) {
    System.out.println(element);
}

了解ArrayList

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

在高并发添加数据的情况下，ArrayList 会暴露以下三个问题：

  1. 部分值为 null（此前我们没有插入过 null 值）
  2. 索引越界
  3. 数组的 size 大小与插入 add 情况不一致

原因分析

ArrayList 的 add 方法源码如下：

1
2
3
4
5
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // step1: 确保数组有足够的空间
    elementData[size++] = e;           // step2: 在 size 索引位置设置值，并维护 size 值加 1
    return true;
}

可以看到，插入一个元素的操作分为三步：

  1. step1：判断当前数组空间是否足够插入一个元素，不够则调用 grow 方法扩容。
  2. step2：在 size 索引位置设置值为新插入的元素。
  3. step3：维护 size 值加 1。
ArraryList新增元素

问题根源

1. 部分值为 null：

在高并发情况下，多个线程可能同时执行 elementData[size] = e;，导致某些线程覆盖了其他线程插入的值，也就是在同一个索引位置设置值，但最后不同的线程都会给size++，最终导致部分值为 null。

2. 索引越界：

线程1走到扩容那里发现当前size是9，数组容量是10不用扩容，cpu让出执行权，线程2也发现不用扩容，这时候数组的容量就是10，而线程1 set完之后size++，这时候线程2再进来size就是
10，数组的大小只有10，而你要设置下标索引为10的就会越界(数组的下标索引从0开始):

3. 数组的 size 大小与插入 add 情况不一致：

由于 size++ 操作不是原子的，多个线程同时执行 size++ ，可能取得size值都是同一个(比如size为10，线程1将把size赋值为11，在线程1未完成赋值时线程二也在执行，此时获取到的size值还是10，最后执行了两次size++，实际上只有效一次size++)，会导致 size 值与实际插入的元素数量不一致。

如何将ArrayList变成线程安全的？

ArrayList 是 Java 中常用的动态数组实现，但它并非线程安全。这意味着在多线程环境下，多个线程同时访问和修改 ArrayList 可能会导致数据不一致或其他并发问题。

使用 Collections.synchronizedList()

1
List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());

底层实现：

Collections.synchronizedList() 方法会返回一个包装了原始 ArrayList 的同步视图。其底层实现原理是为每个方法调用添加一个同步块（synchronized block），确保同一时刻只有一个线程可以访问该列表。

使用 CopyOnWriteArrayList

1
List<String> copyOnWriteList = new CopyOnWriteArrayList<>();

底层实现：

CopyOnWriteArrayList 是 java.util.concurrent 包中的一个线程安全列表实现。其核心思想是**写时复制 (Copy-On-Write)**：当列表发生修改时，会创建一个列表的副本，并在副本上进行修改，而原始列表保持不变。

手动同步

1
2
3
4
5
6
7
8
9
10
11
List<String> list = new ArrayList<>();

// 添加元素时手动同步
synchronized (list) {
    list.add("element");
}

// 获取元素时手动同步
synchronized (list) {
    String element = list.get(0);
}

底层实现：

手动同步需要开发者显式地使用 synchronized 关键字来控制对 ArrayList 的访问。

ArrayList 的扩容机制

当向 ArrayList 中新增元素时，如果下一个索引位置超出了当前数组的容量，则会触发扩容机制。扩容机制的具体步骤如下：

扩容步骤

  1. 计算新的容量：一般情况下，新的容量为原来容量的 1.5 倍。

    • 计算公式：newCapacity = oldCapacity + (oldCapacity >> 1)

  2. 创建新的数组：根据计算出的新容量，创建一个新的数组。

  3. 复制原有数组元素：将原有数组中的元素逐个复制到新的数组中。

  4. 更新引用：将 ArrayList 内部的数组引用更新为新的数组。

  5. 完成扩容：扩容完成后，可以继续插入新的元素。

代码示例

以下是 ArrayList 扩容机制的部分源码：

1
2
3
4
5
6
7
8
9
10
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 计算新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 创建新数组并复制元素
    elementData = Arrays.copyOf(elementData, newCapacity);
}

关键点

  • 扩容因子： 通常为 1.5 倍，但具体实现可能会根据需求调整。
  • 数组复制： 使用 Arrays.copyOf() 方法进行数组复制，效率较高。
  • 内存开销： 扩容会导致内存占用增加，因此在初始化 ArrayList 时，合理设置初始容量可以减少扩容次数，提高性能。

线程安全的 List 如何实现线程安全的？

以 CopyOnWriteArrayList 为例，其底层也是使用数组保存数据。CopyOnWriteArrayList 通过以下方式实现线程安全：

1. 使用 volatile 关键字修饰数组

CopyOnWriteArrayList 使用 volatile 关键字修饰数组，确保线程对数组对象重新赋值后，其他线程可以感知到。

1
private transient volatile Object[] array;

2. 写时复制 (Copy-On-Write) 机制

CopyOnWriteArrayList 的核心思想是**写时复制 (Copy-On-Write)**：当列表发生修改时，会创建一个列表的副本，并在副本上进行修改，而原始列表保持不变。

关键方法：

  • add 方法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();  // 获取锁
        try {
            Object[] elements = getArray();  // 获取当前数组
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);  // 创建新数组
            newElements[len] = e;  // 在新数组中添加元素
            setArray(newElements);  // 更新数组引用
            return true;
        } finally {
            lock.unlock();  // 释放锁
        }
    }

  • setArray 方法：

    1
    2
    3
    final void setArray(Object[] a) {
        array = a;  // 更新数组引用
    }

3. 读操作无需加锁

由于写操作是在副本上进行的，读操作可以直接访问原始数组，无需加锁，从而提高了读操作的性能。

4. 使用 ReentrantLock 保证写操作的线程安全

在写操作（如 add、remove 等）时，CopyOnWriteArrayList 使用 ReentrantLock 保证同一时刻只有一个线程可以进行写操作，从而确保线程安全。