详解常用集合和映射中的线程安全问题

1. 前言

• 在 Java 中，集合和映射是常用的数据结构，它们分为线程安全和线程不安全两类。
• 我们常用的集合包括：ArrayList、HashSet、CopyOnWriteArrayList、CopyOnWriteArraySet。常用的映射包括：HashMap、ConcurrentHashMap、Hashtable（Properties）。
• 下文我们来详细分析其中的线程安全问题。

2. 线程不安全的集合与映射类

2.1 ArrayList

2.1.1 特点

ArrayList 是基于动态数组实现的，它允许存储 null 元素，并且可以根据需要动态调整数组大小。在单线程环境下，ArrayList 的性能表现良好，支持快速随机访问。

2.1.2 ArrayList 线程不安全的原因

ArrayList 的核心是一个动态数组，当元素数量超过数组容量时，会进行扩容操作。同时，它内部有一个 modCount 变量用于记录集合结构被修改的次数，以保证迭代器的一致性。

在多线程环境下，多个线程可以同时访问和修改 ArrayList 的内部状态，而 ArrayList 并没有对这些操作进行同步控制，这就可能导致数据不一致、数组越界、并发修改异常等问题。

2.1.2.1 多线程同时调用 add 方法可能出现的问题

1. 数据覆盖问题
ArrayList 的 add 方法的核心逻辑大致如下：

在多线程环境下，假设有两个线程 A 和 B 同时调用 add 方法。当线程 A 和线程 B 同时执行到 ensureCapacityInternal(size + 1) 时，由于此时 size 的值相同，它们都会认为数组容量足够，不需要进行扩容。然后线程 A 先执行 elementData[size++] = e，将元素添加到数组末尾并将 size 加 1。同时线程 B 执行 elementData[size++] = e，线程 B 的元素将覆盖线程 A 添加的元素，导致数据丢失。
2. 数组越界问题
ArrayList 在进行扩容时，会创建一个新的数组，并将原数组中的元素复制到新数组中。如果多个线程同时触发扩容操作，可能会导致数组越界异常。

例如，当数组容量为 10，size 为 9 时，两个线程同时调用 add 方法，都发现需要扩容。其中一个线程先完成扩容操作，将数组容量扩大到 15。而另一个线程并不知道数组已经扩容，仍然按照原来的容量进行操作，当它尝试将元素添加到数组的第 10 个位置时，就会抛出 ArrayIndexOutOfBoundsException 异常。

3. ConcurrentModificationException 问题
ArrayList 的迭代器是快速失败（fail-fast）的，它会通过 modCount 变量来检测集合结构是否被修改。在多线程环境下，如果一个线程正在使用迭代器遍历 ArrayList，而另一个线程同时调用 add 方法修改了集合的结构，迭代器会检测到 modCount 的变化，从而抛出 ConcurrentModificationException 异常。

2.2 LinkedList

2.2.1 特点

LinkedList 是基于双向链表实现的，它实现了 List 和 Deque 接口，因此可以作为列表、栈或队列使用。它在插入和删除元素时性能较好，尤其是在列表的头部或尾部。

2.2.2 线程不安全的体现

2.3 HashMap

2.3.1 特点

• HashMap 是基于哈希表实现的，它允许使用 null 作为键和值。它提供了快速的插入、查找和删除操作，平均时间复杂度为 O(1)。
  

2.3.1.1 红黑树

红黑树的节点继承了LinkedHashMap.Entry<K,V>，继而继承了Node。

2.3.2 HashMap线程不安全的原因

HashMap 线程不安全主要体现在多线程环境下可能出现数据丢失、死循环、数据不一致等问题，以下是具体原因分析：
1. 数据结构与操作特点
HashMap 是基于哈希表实现的，通过哈希函数计算键的哈希值来确定键值对在数组中的存储位置。在进行插入、删除和查找操作时，通常需要先计算哈希值，再根据哈希值确定在数组中的索引位置。

• 哈希冲突处理：当不同的键计算出相同的哈希值时，就会发生哈希冲突。HashMap 采用链地址法来解决哈希冲突，即每个数组元素是一个链表的头节点，当发生哈希冲突时，新的键值对会以链表节点的形式插入到对应位置的链表中。
• 操作的非原子性：HashMap 的插入、删除等操作通常不是原子的，涉及多个步骤。例如，在插入一个键值对时，需要计算哈希值、确定索引位置、检查是否存在相同键、更新链表或数组等多个操作。在多线程环境下，如果多个线程同时进行插入操作，这些操作可能会相互干扰，导致数据不一致或丢失。
  
  2. 多线程并发操作问题
• 扩容时的并发问题
  • 多线程同时扩容：在多线程环境下，可能会出现多个线程同时检测到 HashMap 需要扩容的情况。每个线程都可能会执行扩容操作，各自创建新的更大容量的数组，并尝试将原数组中的键值对重新哈希到新数组中。这会导致键值对在多个线程之间被重复处理或丢失，最终 HashMap 中的数据可能会出现混乱或不完整。
    
  • 数据迁移冲突：在扩容过程中，需要将原数组中的数据重新分配到新的数组中。如果两个线程同时进行数据迁移，可能**会导致链表结构被破坏。**例如，线程A正在处理某个链表节点，将其迁移到新数组的某个位置，而线程B同时也在处理同一个链表节点，可能会导致链表的指针指向错误，最终导致数据丢失或无法正确访问。
• 插入操作时的并发问题
  • 哈希冲突导致数据覆盖：当多个线程同时向 HashMap 中插入键值对时，如果这些键值对发生哈希冲突，即它们的哈希值相同，可能会导致数据覆盖。例如，线程A和线程B同时插入两个不同的键值对，但它们的哈希值相同，都应该插入到同一个链表位置。由于线程执行的不确定性，可能会导致其中一个键值对覆盖另一个键值对，造成数据丢失。
  • 链表插入顺序混乱：在处理哈希冲突时，新的键值对需要插入到链表的头部或尾部。在多线程环境下，多个线程可能同时尝试向同一个链表插入节点，这可能会导致链表的插入顺序混乱，破坏链表的结构，进而影响后续的查找和遍历操作。
• 迭代过程中的并发修改问题：当一个线程正在对 HashMap 进行迭代操作（如遍历 HashMap 中的所有键值对）时，另一个线程可能同时对 HashMap 进行了插入、删除或修改操作。这可能会导致迭代器出现异常行为，如抛出 ConcurrentModificationException 异常，或者迭代到不完整或不正确的数据。
  

2.4 HashSet

2.4.1 特点

HashSet 是基于 HashMap 实现的，它不允许存储重复元素，并且不保证元素的顺序。

3. 线程安全的集合与映射类

3.1 Vector

• 特点：Vector 也是基于动态数组实现的，和 ArrayList 类似，但它是线程安全的。Vector 的方法大多使用 synchronized 关键字修饰，保证了在多线程环境下的操作是线程安全的。
  

3.2 Hashtable

• 特点：Hashtable 是基于哈希表实现的，和 HashMap 类似，但它是线程安全的。Hashtable 不允许使用 null 作为键或值，并且它的方法也是同步的。
• 性能问题：同样由于使用了同步机制，Hashtable 的性能不如 HashMap，尤其是在高并发场景下。
  

这里补充说明一下为什么Properties要使用Hashtable而不是HashMap？

Properties 类使用 Hashtable 而不是 HashMap 主要有历史原因、线程安全以及对属性文件处理的适配性等方面的考虑，具体如下：

历史原因

• Properties 类诞生于Java早期版本，在当时，Hashtable 是Java中提供的主要哈希表实现类。Properties 类被设计用于处理配置文件等属性信息，在其最初设计时选择了当时已有的 Hashtable 作为底层存储结构，这在一定程度上是为了利用 Hashtable 已有的功能和特性，并且与当时的Java生态和设计理念相契合。

线程安全

• Hashtable 是线程安全的哈希表实现，它的方法大多是通过 synchronized 关键字来实现同步的，这意味着在多线程环境下，多个线程可以安全地访问和操作 Hashtable，而不会出现数据不一致或并发访问错误等问题。
• Properties 通常会在多个线程可能同时访问的场景中使用，例如在读取和修改配置文件属性时，多个线程可能需要同时访问 Properties 对象。使用 Hashtable 作为底层结构可以确保在这些场景下的线程安全性，而不需要额外的同步措施。
• 虽然 HashMap 也可以通过一些方式（如使用 Collections.synchronizedMap 方法）来实现线程安全，但这需要额外的代码和操作，相比之下，Hashtable 原生的线程安全特性更符合 Properties 对线程安全的需求。

3.3 ConcurrentHashMap

3.3.1 特点

ConcurrentHashMap 是线程安全的哈希表实现，它采用了 CAS（Compare-And-Swap）和 synchronized 关键字，在多线程环境下具有较高的并发性能。它允许使用 null 作为值，但不允许使用 null 作为键。

3.3.2 保障线程安全的措施

下面从初始化、插入、扩容和读取等方面详细解释其线程安全的实现机制。

3.3.2.1 初始化

ConcurrentHashMap 的初始化是懒加载的，在第一次插入元素时才会进行初始化操作。初始化操作使用 CAS 来保证只有一个线程可以成功初始化数组，避免多个线程同时初始化导致的问题。

在上述代码中，U.compareAndSwapInt 是一个 CAS 操作，通过比较 SIZECTL 的值是否等于 sc，如果相等则将其更新为 -1，表示当前线程正在进行初始化操作。

3.3.2.2 插入操作

插入元素时，ConcurrentHashMap 首先计算键的哈希值，然后找到对应的桶。对于不同的情况，采用不同的线程安全策略：

• 桶为空：使用 CAS 操作将新节点插入到桶中，确保只有一个线程可以成功插入。
  
• 桶不为空且是链表结构：使用 synchronized 关键字对链表头节点加锁，然后遍历链表进行插入操作，保证同一时间只有一个线程可以修改该链表。
  
• 桶不为空且是红黑树结构：同样使用 synchronized 关键字对红黑树的根节点加锁，然后进行插入操作。

fh的含义

• fh 代表当前桶的头节点的哈希值，代码里一般是通过 f.hash 获取的，这里的 f 就是当前桶的头节点。

• 不同的哈希值有不同的含义：
  fh >= 0：表示当前桶存储的是链表结构。因为链表节点的哈希值通常是正常计算得到的，为非负数。
  fh == MOVED：MOVED 是一个常量（值为 -1），代表当前桶的头节点是 ForwardingNode，意味着该桶已经完成迁移，正在进行扩容操作。
  fh == TREEBIN：TREEBIN 是一个常量（值为 -2），表示当前桶存储的是红黑树结构。
  fh == RESERVED：RESERVED 是一个常量（值为 -3），表示当前桶正在进行计算操作。

3.3.2.3 扩容操作

当元素数量达到一定阈值时，ConcurrentHashMap 会进行扩容操作。扩容操作是多线程协作完成的，每个线程负责迁移一部分桶的数据。在迁移过程中，使用 ForwardingNode 标记已经迁移的桶，其他线程在访问这些桶时会协助进行迁移。通过这种方式，避免了多个线程同时修改同一个桶的数据，保证了扩容操作的线程安全。

3.3.2.4 读取操作

读取操作是无锁的，因为 ConcurrentHashMap 的节点使用 volatile 关键字修饰，保证了节点的可见性。当一个线程修改了节点的值，其他线程可以立即看到最新的值。因此，读取操作不需要加锁，提高了并发性能。

3.4. CopyOnWriteArrayList

3.4.1 特点

CopyOnWriteArrayList 是线程安全的列表实现，它采用了写时复制的策略。当进行写操作（如添加、删除元素）时，会创建一个新的数组副本，在副本上进行修改，然后将原数组引用指向新的数组。

• 适用场景：适用于读多写少的场景，因为写操作的开销较大。
  

3.4.2 有Lock控制并发为什么还需要写时复制？

CopyOnWriteArrayList 采用 ReentrantLock 保证并发安全的同时使用写时复制（Copy-On-Write）策略，主要是为了在保证线程安全的基础上，尽可能地提高读操作的性能，同时减少锁的粒度和对读操作的影响，下面从几个方面详细阐述其原因。

1. 读写分离以提升读性能

• 读操作无锁：写时复制策略允许在进行读操作时无需加锁。当多个线程进行读操作时，它们可以直接访问当前的数组，不会因为锁的竞争而阻塞。这是因为读操作读取的是原数组的内容，而写操作会在新的数组副本上进行修改，两者相互独立。
• 高并发读场景优势：在实际应用中，很多场景下读操作的频率远远高于写操作。

2. 保证数据一致性和线程安全

• 写操作加锁：虽然写时复制策略本身不能完全保证线程安全，但 CopyOnWriteArrayList 在写操作时使用 ReentrantLock 进行加锁。当一个线程进行写操作（如 add、remove 等）时，会先获取锁，确保同一时间只有一个线程可以进行写操作。
• 复制与替换：获取锁后，写操作会创建一个原数组的副本，在副本上进行修改。修改完成后，再将原数组的引用指向新的数组副本。这样可以保证在写操作过程中，读操作仍然可以访问原数组，不会受到写操作的影响，从而保证了数据的一致性和线程安全。

3. 减少锁的粒度和影响范围

• 锁仅用于写操作：CopyOnWriteArrayList 只在写操作时加锁，锁的粒度相对较小。相比一些传统的线程安全列表（如 Vector），Vector 的所有操作（包括读操作和写操作）都使用 synchronized 关键字进行同步，这会导致在高并发读场景下，大量线程会因为锁的竞争而阻塞，性能受到严重影响。
• 降低锁的持有时间：写时复制策略使得写操作在副本上进行，减少了锁的持有时间。因为写操作只需要在创建副本和替换原数组引用时持有锁，而在实际的修改操作过程中不需要持有锁，从而降低了锁的竞争程度，提高了并发性能。

4. 简化并发控制逻辑

• 避免复杂的读写锁机制：写时复制策略避免了使用复杂的读写锁机制。读写锁虽然可以提高并发性能，但需要更复杂的实现和管理，容易出现死锁等问题。而 CopyOnWriteArrayList 的写时复制策略通过简单的复制和替换操作，结合 ReentrantLock 进行写操作的同步，简化了并发控制逻辑，降低了开发和维护的难度。

3.5 CopyOnWriteArraySet

• 特点：CopyOnWriteArraySet 是线程安全的集合实现，它基于 CopyOnWriteArrayList 实现，不允许存储重复元素。同样采用写时复制策略。
• 适用场景：适用于读多写少的场景。
  
  

这里注意一下CopyOnWriteArraySet虽然是HashSet的并发替代。然而两者底层实现毫无关联。