Java 多线程编程之六集合类的线程安全问题

大纲

• Java 多线程编程之一 Java 内存模型浅析
• Java 多线程编程之二 synchronize 锁对象竞争
• Java 多线程编程之三 volatile 与 JMM 内存模型
• Java 多线程编程之四 CAS、ABA 问题、锁
• Java 多线程编程之五 AQS 底层源码深度剖析
• Java 多线程编程之六集合类的线程安全问题
• Java 多线程编程之七队列、线程池、线程通信
• Java 多线程编程之八 Fork/Join 框架使用
• Java 多线程编程之九 ThreadLocal 使用

集合类的简单介绍

常见的集合类有哪些

Java 中的集合类分为存储值（Collection）、存储键值对（Map）两种类型。Map 接口和 Collection 接口是所有集合框架的父接口，其中 Collection 接口的子接口包括 List 接口、Set 接口、Queue 接口。

• List 接口的实现类主要有：ArrayList、LinkedList、Vector、Stack 等
• Set 接口的实现类主要有：HashSet、LinkedHashSet、TreeSet 等
• Queue 接口的实现类主要有：ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityBlockingQueue、DelayedWorkQueue 等

• Map 接口的实现类主要有：HashMap、HashTable、ConcurrentHashMap、TreeMap 等

队列的使用

更多关于队列的使用教程，请阅读 这里。

常见的并发容器有哪些

常见的并发容器（线程安全）有以下几种：

• ConcurrentHashMap：是一个线程安全的 HashMap，它支持高并发的读和写，是 Java 中最常用的并发 Map 实现之一。
• CopyOnWriteArraySet：是一个线程安全的 Set，它通过对数据进行复制来保证线程安全，在写操作时会对数据进行复制，并进行写操作，读操作则不需要进行复制。
• CopyOnWriteArrayList：是一个线程安全的 ArrayList，它通过对数据进行复制来保证线程安全，在写操作时会对数据进行复制，并进行写操作，读操作则不需要进行复制。
• BlockingQueue：是一个阻塞队列，它可以在队列为空或队列已满时，暂停生产者线程或消费者线程的执行，从而避免了数据竞争和资源浪费。
• ConcurrentLinkedQueue：是一个非阻塞的队列，它可以支持高并发访问，并且性能优于 BlockingQueue。
• PriorityQueue：是一种优先队列，它可以实现按照优先级排序的队列，可用于解决某些求最小值或最大值的算法问题。
• ConcurrentSkipListMap、ConcurrentSkipListSet：是一种高并发的跳表，它可以支持高效的并发读写操作。

HashMap 和 HashTable 的区别

HashMap 和 HashTable 都是 Java 中用于存储键值对的数据结构，它们之间有以下几点区别：

• 线程安全性：HashTable 是线程安全的，而 HashMap 是非线程安全的。
• null 键值：在 HashMap 中，可以存储一个键或值为 null 的元素，如果尝试将相同的键多次放入 HashMap 中，后面的值会覆盖前面的值。相反的，在 HashTable 中，不允许键或值为 null。
• 继承关系：HashMap 继承自 AbstractMap 类，而 HashTable 继承自 Dictionary 类，两者都实现了 Map 接口。
• 性能方面：HashMap 的性能比 HashTable 更高，因为 HashTable 在每次访问时都需要进行同步处理，而 HashMap 不需要同步，因此在单线程环境下 HashMap 的性能更高。

总结说明

• 如果不需要线程安全，并且有可能会存储 null 键或值，推荐使用 HashMap。
• 如果需要线程安全，建议使用 ConcurrentHashMap，而避免使用 HashTable，因为它已经被官方标记为不推荐使用。
• ConcurrentHashMap 通过把整个 Map 分为 N 个 Segment（类似 HashTable），可以提供相同的线程安全，但是性能提升 N 倍，性能默认提升 16 倍。

ArrayList 的线程不安全

ArrayList 的扩容机制

当执行 new ArrayList<Integer>() 操作时，底层创建了一个空的数组，且数组的初始长度为 10。当向 ArrayList 添加元素时，如果当前元素个数达到了数组的容量，就会触发扩容操作。ArrayList 的扩容机制是通过调用 grow() 方法来实现的，而 grow() 方法则是调用 Arrays.copyOf(elementData, netCapacity) 方法进行扩容。具体的扩容过程如下：

• (1) 当创建 ArrayList 对象时，会初始化一个默认容量（一般为 10）的数组作为底层存储结构。
• (2) 当添加新元素时，会首先判断是否需要扩容，即判断当前元素个数是否已经达到数组容量。
• (3) 如果需要进行扩容，ArrayList 会计算新的容量大小，一般是当前容量的 1.5 倍（即旧容量 * 1.5）。
• (4) 然后会创建一个新的数组，并将原数组中的元素复制到新数组中。
• (5) 最后，ArrayList 会将新数组设置为内部存储数组，并丢弃旧数组。

ArrayList 的并发修改

为什么 ArrayList 是线程不安全的呢？因为在进行执行写操作的时候，方法上为了保证并发性，是没有添加 synchronized 修饰的，所以在并发写的时候，就会出现问题。

public class ArrayListTest {

    public static void main(String[] args) throws InterruptedException {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            // ArrayList 不支持并发写操作
            new Thread(() -> {
                list.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(list);
            }, String.valueOf(i)).start();
        }
    }

}

程序运行输出的结果：

java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1043)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:997)
	at java.base/java.util.AbstractCollection.toString(AbstractCollection.java:472)
	at java.base/java.lang.String.valueOf(String.java:2951)
	at java.base/java.io.PrintStream.println(PrintStream.java:897)
	at com.java.interview.test.ArrayListTest.lambda$main$0(ArrayListTest.java:14)
	at java.base/java.lang.Thread.run(Thread.java:834)

解决 ArrayList 并发写出现的异常：

• 第一种方法：使用 JUC 里面的 CopyOnWriteArrayList （写时复制）类替代，其底层实现主要是一种读写分离的思想。
• 第二种方法：使用 Collectons 类，即使用 Collections.synchronizedList(new ArrayList<>()) 创建一个线程安全的 List。
• 第三种方法：使用 Vector 替代，Vector 底层是使用数组实现的，在每个方法上都加了锁，即使用 synchronized 修饰方法，这导致了其运行效率特别低。

ArrayList 的写时复制

写时复制的实现原理

CopyOnWrite 容器即写时复制的容器。往一个容器添加元素的时候，不直接往当前容器的 Object[] 添加，而是先将当前 Object[] 进行 Copy，复制出一个新的容器 Object[] newElements，然后新的容器 Object[] newElements 里添加元素，添加完元素之后，再将原容器的引用指向新的容器（setArray（newElements））。这样做的好处是可以对 CopyOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素，所以 CopyOnWrite 容器也是一种读写分离的思想，读和写针对的是不同的容器。JDK 8 的 CopyOnWriteArrayList 的底层源码如下：

写时复制的使用案例

这里简单介绍一下 CopyOnWriteArrayList 的使用，可以用于解决 ArrayList 的线程安全问题，示例代码如下：

public class ArrayListTest {

    public static void main(String[] args) throws InterruptedException {
        List<String> list = new CopyOnWriteArrayList<>();
        for (int i = 1; i <= 10; i++) {
            // CopyOnWriteArrayList 支持并发写操作
            new Thread(() -> {
                list.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(list);
            }, String.valueOf(i)).start();
        }
    }

}

程序运行输出的结果：

[9d12f701]
[9d12f701, 77f4feca, eb280a00]
[9d12f701, 77f4feca]
[9d12f701, 77f4feca, eb280a00, 859da88c, 3204da31, 0b594f8c, ff2a1328]
[9d12f701, 77f4feca, eb280a00, 859da88c, 3204da31, 0b594f8c]
[9d12f701, 77f4feca, eb280a00, 859da88c, 3204da31]
[9d12f701, 77f4feca, eb280a00, 859da88c]
[9d12f701, 77f4feca, eb280a00, 859da88c, 3204da31, 0b594f8c, ff2a1328, 6515bf2e, 175fb2da, 97a3832a]
[9d12f701, 77f4feca, eb280a00, 859da88c, 3204da31, 0b594f8c, ff2a1328, 6515bf2e, 175fb2da]
[9d12f701, 77f4feca, eb280a00, 859da88c, 3204da31, 0b594f8c, ff2a1328, 6515bf2e]

写时复制的优缺点

• 优点

  • 适用于读多写少的业务场景，可以提高并发性能。

• 缺点

  • 存在内存占用问题、数据一致性问题。
  • 为了减少扩容带来开销，应该尽量使用批量添加（减少复制次数）。
  • CopyOnWrite 机制只能保证数据的最终一致性，不能保证实时数据的强一致性，因此如果希望写入的数据能马上能读到，那么就不能使用 CopyOnWrite 机制。

HashSet 的线程不安全

HashSet 的底层结构

HashSet 的底层是使用 HashMap 进行实现的。

为什么调用 HashSet 的 add() 方法时，只需要传递一个参数，而 HashMap 是则需要传递 key-value 键值对呢？首先查看 HashSet 的 add() 方法（如下图），可以发现在调用 add() 方法的时候，新增的值只是作为 key，而 value 存储的是一个 Object 类型的常量。也就是说 HashSet 在存储数据时，只关心 key，而不关心 value。

HashSet 的并发修改

为什么 HashSet 是线程不安全的呢？因为在进行执行写操作的时候，方法上为了保证并发性，是没有添加 synchronized 修饰的，所以在并发写的时候，就会出现问题。

public class HashSetTest {

    public static void main(String[] args) throws InterruptedException {
        Set<String> set = new HashSet<>();
        for (int i = 1; i <= 10; i++) {
            // HashSet 不支持并发写操作
            new Thread(() -> {
                set.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(set);
            }, String.valueOf(i)).start();
        }
    }

}

程序运行输出的结果：

java.util.ConcurrentModificationException
	at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1493)
	at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1516)
	at java.base/java.util.AbstractCollection.toString(AbstractCollection.java:472)
	at java.base/java.lang.String.valueOf(String.java:2951)
	at java.base/java.io.PrintStream.println(PrintStream.java:897)
	at com.java.interview.test.HashSetTest.lambda$main$0(HashSetTest.java:15)
	at java.base/java.lang.Thread.run(Thread.java:834)

解决 HashSet 并发写出现的异常：

• 第一种方法：使用 CopyOnWriteArraySet（写时复制）类替代，其底层实现主要是一种读写分离的思想。
• 第二种方法：使用 Collectons 类，即使用 Collections.synchronizedSet(new HashSet<>()) 创建一个线程安全的 HashSet。

HashSet 的写时复制

写时复制的实现原理

CopyOnWriteArraySet 的底层是使用 CopyOnWriteArrayList 进行实例化。

写时复制的使用案例

这里简单介绍一下 CopyOnWriteArraySet 的使用，可以用于解决 HashSet 的线程安全问题，示例代码如下：

public class HashSetTest {

    public static void main(String[] args) throws InterruptedException {
        Set<String> set = new CopyOnWriteArraySet<>();
        for (int i = 1; i <= 10; i++) {
            // CopyOnWriteArraySet 支持并发修改
            new Thread(() -> {
                set.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(set);
            }, String.valueOf(i)).start();
        }
    }

}

程序运行输出的结果：

[3c2e0351]
[3c2e0351, 8f987008, 9b0e5b7d]
[3c2e0351, 8f987008]
[3c2e0351, 8f987008, 9b0e5b7d, 06eddb63, 7d4ca880, d68de36d]
[3c2e0351, 8f987008, 9b0e5b7d, 06eddb63, 7d4ca880]
[3c2e0351, 8f987008, 9b0e5b7d, 06eddb63]
[3c2e0351, 8f987008, 9b0e5b7d, 06eddb63, 7d4ca880, d68de36d, 1e8ce86f, 0c4f7d93, 524f3f78, 31ef5f4a]
[3c2e0351, 8f987008, 9b0e5b7d, 06eddb63, 7d4ca880, d68de36d, 1e8ce86f, 0c4f7d93, 524f3f78]
[3c2e0351, 8f987008, 9b0e5b7d, 06eddb63, 7d4ca880, d68de36d, 1e8ce86f, 0c4f7d93]
[3c2e0351, 8f987008, 9b0e5b7d, 06eddb63, 7d4ca880, d68de36d, 1e8ce86f]

HashMap 的线程不安全

HashMap 的并发修改

为什么 HashMap 是线程不安全的呢？因为在进行执行写操作的时候，方法上为了保证并发性，是没有添加 synchronized 修饰的，所以在并发写的时候，就会出现问题。

public class HashMapTest {

    public static void main(String[] args) throws InterruptedException {
        Map<String, String> set = new HashMap<>();
        for (int i = 1; i <= 10; i++) {
            // HashMap 不支持并发写操作
            new Thread(() -> {
                String str = UUID.randomUUID().toString().substring(0, 8);
                set.put(str, str);
                System.out.println(set);
            }, String.valueOf(i)).start();
        }
    }

}

java.util.ConcurrentModificationException
	at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1493)
	at java.base/java.util.HashMap$EntryIterator.next(HashMap.java:1526)
	at java.base/java.util.HashMap$EntryIterator.next(HashMap.java:1524)
	at java.base/java.util.AbstractMap.toString(AbstractMap.java:551)
	at java.base/java.lang.String.valueOf(String.java:2951)
	at java.base/java.io.PrintStream.println(PrintStream.java:897)
	at com.java.interview.test.HashMapTest.lambda$main$0(HashMapTest.java:16)
	at java.base/java.lang.Thread.run(Thread.java:834)

解决 HashMap 并发写出现的异常：

• 第一种方法：使用 ConcurrentHashMap 替代，即使用 Map<String, String> map = new ConcurrentHashMap<>()。
• 第二种方法：使用 Collectons 类，即使用 Collections.synchronizedMap(new HashMap<>()) 创建一个线程安全的 Map。

List 的并发迭代修改

• 普通 List

  • 在单线程环境下，普通的 List 默认不支持在迭代时，动态对容器进行插入、更改、删除等写操作，否则会抛出 ConcurrentModificationException 异常。
  • 这是因为迭代器并不知道列表在迭代过程中是否发生了结构性修改，可以使用 ListIterator 来解决。

• CopyOnWriteArrayList

  • 在多个线程环境中，CopyOnWriteArrayList 支持并发访问，而且支持在迭代过程中对容器进行结构性修改，而且不需要借助 ListIterator。
  • 这是因为容器每次修改时会创建一个新的容器副本（使用写时复制技术），然后再对新的容器副本进行修改，也就是说迭代的容器和修改的容器不是同一个，所以使用迭代器遍历容器不受修改的影响。

• Collections.synchronizedList()

  • 使用 Collections.synchronizedList() 创建的同步列表，支持在多个线程间安全地进行同步访问，但它并不完全支持并发修改。
  • 具体来说，它在多个线程并发访问时，通过同步机制来保证每次只有一个线程可以访问该 List，从而避免数据不一致的问题。但是，这种同步机制并不支持多个线程在迭代过程中对容器进行结构性修改，否则会抛出 ConcurrentModificationException 异常，即使使用 ListIterator 也解决不了。
  • 这是因为 Collections.synchronizedList() 通过内部的同步机制来保证单个操作的原子性，但不能保证迭代操作和修改操作之间的并发一致性。当在一个线程中使用 ListIterator 进行迭代时，另一个线程可以在任何时间对列表进行结构性修改（如添加、删除元素），这会导致迭代器检测到集合的并发修改，进而抛出异常。
  • ListIterator 使用快速失败（Fail-Fast）机制来检测集合的并发修改。每当集合进行结构性修改时，都会更新一个修改计数器（modCount）。当迭代器检测到集合的 modCount 与创建时的 modCount 不一致时，就会抛出 ConcurrentModificationException 异常。这种机制是在同步列表中同样适用的，因为同步列表并没有提供防止 modCount 变化的额外保护。
  • 为了解决不支持在迭代过程中对容器进行结构性修改的问题，可以使用 CopyOnWriteArrayList 或者 ReentrantLock 来解决。

案例代码一

public class CopyOnWriteArrayListTest {

    public static void main(String[] args) {

        // Runnable task = new Task1();  // 抛出异常
        
        Runnable task = new Task2();     // 正常运行

        for (int i = 0; i < 10; i++) {
            new Thread(task).start();
        }
    }

}

class Task1 implements Runnable {

    // 在单线程环境下，不支持在迭代过程中对容器进行结构性修改，因为在同步列表内部，迭代器并不知道列表在迭代过程中是否发生了结构性修改，可以使用 ListIterator 来解决
    // 在多线程环境下，支持并发访问，但不支持在迭代过程中对容器进行结构性修改，即使使用 ListIterator 进行迭代也解决不了
    private static List<String> list = Collections.synchronizedList(new ArrayList<>());

    static {
        list.add("AAA");
        list.add("BBB");
        list.add("CCC");
    }

    @Override
    public void run() {
        ListIterator<String> iterator = list.listIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
            iterator.add("DDD");
        }
    }

}

class Task2 implements Runnable {

    // 在多线程环境下，支持并发访问，且支持在迭代过程中对容器进行结构性修改
    // 因为容器每次修改时会创建一个新的容器副本，也就是说修改的容器和迭代的容器不是同一个，所以使用迭代器遍历容器不受修改的影响
    private static List<String> list = new CopyOnWriteArrayList<>();

    static {
        list.add("AAA");
        list.add("BBB");
        list.add("CCC");
    }

    @Override
    public void run() {
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
            list.add("DDD");
        }
    }

}

案例代码二

针对 Collections.synchronizedList() 不支持多个线程在迭代过程中对容器进行结构性修改的问题，即使在遍历集合时使用 synchronized 块进行显式同步，也只能保证单个线程在该同步块内的操作是线程安全的。但如果另一个线程在同步块外对集合进行修改，这种结构性变化仍会被迭代器检测到，并抛出异常。

public class Test {
    public static void main(String[] args) {

        List<String> syncList = Collections.synchronizedList(new ArrayList<>(List.of("A", "B", "C")));

        // 一个线程用于迭代
        new Thread(() -> {
            synchronized (syncList) {
                Iterator<String> iterator = syncList.iterator();
                while (iterator.hasNext()) {
                    System.out.println("Iterating: " + iterator.next());
                    try {
                        // 模拟迭代操作耗时
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }).start();

        // 另一个线程用于修改
        new Thread(() -> {
            try {
                // 确保修改线程在迭代线程开始后执行
                Thread.sleep(50);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
            synchronized (syncList) {
                syncList.add("D");
                System.out.println("Added D");
            }
        }).start();
    }

}

上述的代码可能会抛出 ConcurrentModificationException 异常，因为两个线程分别进行迭代和修改操作，即使同步块保证了单个操作的线程安全，但无法保证多个操作（整体）的并发一致性。