{T}

并发容器

HashMap 的线程不安全问题

HashMap 是使用非常多的容器，也是 Map 最主要的实现类之一，但其自身不具备线程安全的特点，可从多种情况体现。

源码分析

HashMap 的 put 方法源码：

java
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
//modCount++ 是一个复合操作
    modCount++;
 
addEntry(hash, key, value, i);
    return null;
}

modCount++ 是典型的"i++"操作，属于线程不安全的"运行结果错误"情况。i++ 并非原子操作，其执行分三步，每步之间都可能被打断：

  • 读取；
  • 增加；
  • 保存。

线程不安全发生过程如下：

线程 1 先拿到 i=1，进行 i+1 操作但未保存，随后被切换走；线程 2 执行相同 i++ 操作，拿到的 i 仍为 1（线程 1 结果未保存，线程 2 不可见）。线程 2 完成 +1 后切回线程 1，保存结果 2；再切回线程 2 保存 i=2。两个线程各执行一次 +1，最终却只得到 i=2 而非 i=3，导致数据结果错误。

从源码角度足以证明 HashMap 线程不安全。多个线程同时调用 put() 时可能算错 modCount 值（以上为 Java 7 源码；Java 8 的 put 调用 putVal 方法，内部同样有 ++modCount 语句，原理相同）。

实验：扩容期间取出的值不准确

HashMap 默认容量不大，持续添加数据会在合适时机扩容。扩容期间新建空数组，用旧项填充；填充过程中若有线程取值，可能取到 null 而不是原值。演示代码如下：

java
public class HashMapNotSafe {
 
public static void main(String[] args) {
        final Map<Integer, String> map = new HashMap<>();
 
final Integer targetKey = 0b1111_1111_1111_1111; // 65 535
        final String targetValue = "v";
        map.put(targetKey, targetValue);
 
new Thread(() -> {
            IntStream.range(0, targetKey).forEach(key -> map.put(key, "someValue"));
        }).start();
 
while (true) {
            if (null == map.get(targetKey)) {
                throw new RuntimeException("HashMap is not thread safe.");
            }
        }
    }
}

代码建立 HashMap，key 取二进制 1111_1111_1111_1111（十进制 65535），目的是让扩容回填数据时不要太快，便于捕捉错误；value 取非 null 的 "v"。新线程通过 IntStream（0 到 65535 左闭右开）不断往 map 添加 key，value 统一为 "someValue"。主线程进入 while 循环，反复检测 targetKey 对应的值是否为 "v"；若取到 null 则抛出 RuntimeException。

运行结果：

java
Exception in thread "main" java.lang.RuntimeException: HashMap is not thread safe.
at lesson29.HashMapNotSafe.main(HashMapNotSafe.java:25)

程序很快抛出 RuntimeException，证明取到的是 null 而非 "v"，HashMap 线程不安全。

除上述例子外，HashMap 还有其他线程不安全情况：

同时 put 碰撞导致数据丢失

多个线程同时 put，且 key 发生碰撞（hash 计算出的 bucket 位置相同），两个线程同时判断该位置为空可写入，则两个不同 value 添加到同一位置，最终只保留一个数据，丢失一个数据。

可见性问题无法保证

线程安全需保证可见性，即一个线程操作容器时其他线程能感知。HashMap 无法保证：线程 1 给某 key 放入新值，线程 2 获取该 key 时可能看到、也可能看不到此次更改。

死循环造成 CPU 100%

HashMap 扩容逻辑会反转散列桶中的节点顺序。多线程同时扩容时，若两个线程同时反转，可能形成链表循环（A 指向 B，B 指回 A），之后获取 key 对应的 value 时遍历链表永不结束，导致 CPU 100%。

综上，HashMap 线程不安全，多线程场景应避免使用。Collections.synchronizedMap(new HashMap()) 虽线程安全但效率低下（内部大量使用 synchronized，多线程不能同时操作）。推荐使用线程安全且性能较好的 ConcurrentHashMap。

ConcurrentHashMap 在 Java7 与 8 的差异

Java 8 对 ConcurrentHashMap 进行了大幅升级。Java 7 的 Segment 设计思想仍具参考价值。二者结构、原理、性能差异如下。

Java 7 版本的 ConcurrentHashMap

Java 7 版本 ConcurrentHashMap 结构示意图：

ConcurrentHashMap 内部进行 Segment 分段，Segment 继承 ReentrantLock，可视为一把锁，各 Segment 之间独立上锁、互不影响。相比 Hashtable 每次操作锁住整个对象，并发效率大幅提高。

每个 Segment 底层数据结构与 HashMap 类似，为数组和链表组成的拉链法结构。默认有 0~15 共 16 个 Segment，最多同时支持 16 个线程并发操作（分布在不同 Segment 上）。16 为默认值，可在初始化时设置其他值，但一旦确认初始化后不可扩容。

Java 8 版本的 ConcurrentHashMap

Java 8 几乎完全重写 ConcurrentHashMap，代码量从 Java 7 的 1000 多行增至 6000 多行。整体结构示意图：

图中的节点有三种类型：

  • 空位：当前还没有元素填充。
  • 拉链法结构：每个槽先填入第一个节点，后续相同 Hash 值用链表往后延伸。
  • 红黑树结构：Java 7 的 ConcurrentHashMap 所没有的结构。

当链表长度大于阈值（默认 8）且满足一定容量要求时，链表转化为红黑树，提高查找性能。红黑树是每个节点带红色或黑色属性的二叉查找树，本质是对 BST 的平衡策略，查找效率高、自动平衡。

由于自平衡特点（左右子树高度几乎一致），查找性能近似二分查找，时间复杂度 O(log(n))；链表最坏情况需遍历整个链表，时间复杂度 O(n)，节点越多 O(log(n)) 优势越明显。

红黑树其他特点：

  • 每个节点为红色或黑色，根节点永远为黑色。
  • 红色节点不能连续，红色节点的子节点和父节点都不能是红色。
  • 从任一节点到其每个叶子节点的路径包含相同数量的黑色节点。

这些规则保证较高查找效率。Java 8 引入红黑树是为了避免极端情况下冲突链表过长导致查询慢，保证极端情况下查询效率在 O(log(n))。

分析 Java 8 版本的 ConcurrentHashMap 的重要源码

Java 7 已过时，重点分析 Java 8 版本源码。

Node 节点

最基础的内部存储结构 Node：

java
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    // ...
}

每个 Node 是 key-value 形式，value 用 volatile 修饰保证可见性，内部有 next 指针指向下一个节点，形成链表结构。

put 方法源码分析

put 方法核心是 putVal 方法，源码及注释分析：

java
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) {
        throw new NullPointerException();
    }
    //计算 hash 值
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K, V>[] tab = table; ; ) {
        Node<K, V> f;
        int n, i, fh;
        //如果数组是空的，就进行初始化
        if (tab == null || (n = tab.length) == 0) {
            tab = initTable();
        }
        // 找该 hash 值对应的数组下标
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //如果该位置是空的，就用 CAS 的方式放入新值
            if (casTabAt(tab, i, null,
                    new Node<K, V>(hash, key, value, null))) {
                break;
            }
        }
        //hash值等于 MOVED 代表在扩容
        else if ((fh = f.hash) == MOVED) {
            tab = helpTransfer(tab, f);
        }
        //槽点上是有值的情况
        else {
            V oldVal = null;
            //用 synchronized 锁住当前槽点，保证并发安全
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    //如果是链表的形式
                    if (fh >= 0) {
                        binCount = 1;
                        //遍历链表
                        for (Node<K, V> e = f; ; ++binCount) {
                            K ek;
                            //如果发现该 key 已存在，就判断是否需要进行覆盖，然后返回
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent) {
                                    e.val = value;
                                }
                                break;
                            }
                            Node<K, V> pred = e;
                            //到了链表的尾部也没有发现该 key，说明之前不存在，就把新值添加到链表的最后
                            if ((e = e.next) == null) {
                                pred.next = new Node<K, V>(hash, key,
                                        value, null);
                                break;
                            }
                        }
                    }
                    //如果是红黑树的形式
                    else if (f instanceof TreeBin) {
                        Node<K, V> p;
                        binCount = 2;
                        //调用 putTreeVal 方法往红黑树里增加数据
                        if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
                                value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent) {
                                p.val = value;
                            }
                        }
                    }
                }
            }
            if (binCount != 0) {
                //检查是否满足条件并把链表转换为红黑树的形式，默认的 TREEIFY_THRESHOLD 阈值是 8
                if (binCount >= TREEIFY_THRESHOLD) {
                    treeifyBin(tab, i);
                }
                //putVal 的返回是添加前的旧值，所以返回 oldVal
                if (oldVal != null) {
                    return oldVal;
                }
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

putVal 方法根据当前槽点的不同状态（未初始化、空、扩容、链表、红黑树）做出不同处理。

get 方法源码分析

get 方法源码注释分析：

java
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //计算 hash 值
    int h = spread(key.hashCode());
    //如果整个数组是空的，或者当前槽点的数据是空的，说明 key 对应的 value 不存在，直接返回 null
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
        //判断头结点是否就是我们需要的节点，如果是则直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //如果头结点 hash 值小于 0，说明是红黑树或者正在扩容，就用对应的 find 方法来查找
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        //遍历链表来查找
        while ((e = e.next) != null) {
            if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

get 过程总结：

  • 计算 Hash 值，据此找到对应的槽点；
  • 若数组为空或该位置为 null，直接返回 null；
  • 若该位置节点刚好是需要的，直接返回该节点的值；
  • 若该位置节点是红黑树或正在扩容，用 find 方法继续查找；
  • 否则为链表，遍历链表查找。

对比Java7 和Java8 的异同和优缺点

数据结构

Java 7 采用 Segment 分段锁，Java 8 采用数组 + 链表 + 红黑树，二者差异很大。

并发度

Java 7 中每个 Segment 独立加锁，最大并发个数为 Segment 的个数，默认 16。Java 8 锁粒度更细，理想情况下 table 数组元素个数（数组长度）即为支持并发的最大个数，并发度提高。

保证并发安全的原理

Java 7 采用 Segment 分段锁保证安全，Segment 继承自 ReentrantLock。Java 8 放弃 Segment 设计，采用 Node + CAS + synchronized 保证线程安全。

遇到 Hash 碰撞

Java 7 在 Hash 冲突时使用拉链法（链表形式）。Java 8 先使用拉链法，在链表长度超过阈值时转换为红黑树提高查找效率。

查询时间复杂度

Java 7 遍历链表时间复杂度 O(n)，n 为链表长度。Java 8 遍历红黑树时间复杂度 O(log(n))，n 为树的节点个数。

Map 桶转红黑树的阈值

JDK 1.8 的 HashMap 和 ConcurrentHashMap：往 Map 放元素时计算 hash 值，第 1 个 value 占用一个桶（槽点）位置，后续计算结果落到同一桶时用链表形式往后延长，即"拉链法"，如图所示：

图中有的桶为空（第 4 个），有的只有一个元素（1、3、6），有的为拉链法结构（第 2、5 个）。

当链表长度大于或等于阈值（默认 8），且满足容量大于或等于 MIN_TREEIFY_CAPACITY（默认 64）时，链表转换为红黑树。后续若因删除或调整大小使红黑树节点小于或等于 6 个，恢复为链表形态。

HashMap 结构示意图：

图中有空槽点、拉链、红黑树三种形态。

为什么需要转换

每次遍历链表平均查找时间复杂度 O(n)，n 为链表长度。红黑树有自平衡特点，可防止不平衡，始终将查找时间复杂度控制在 O(log(n))。链表短时 O(n) 与 O(log(n)) 差别不大；链表变长后区别显现。为提升查找性能，需将链表转化为红黑树。

为什么不一开始就用红黑树

JDK 源码注释对此作了说明：

java
Because TreeNodes are about twice the size of regular nodes,
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due
removal or resizing) they are converted back to plain bins.

单个 TreeNode 占用的空间约为普通 Node 的两倍，只有包含足够多 Nodes 时才转成 TreeNodes，是否足够由 TREEIFY_THRESHOLD 决定。桶中节点数因移除或 resize 变少后，又变回普通链表以节省空间。

默认链表长度达 8 转红黑树，降到 6 转换回去，体现时间和空间平衡思想。链表短时空间占用少、查询时间无大问题；链表变长后用红黑树保证查询效率。阈值默认取 8，源码对选择 8 的解释如下：

java
In usages with well-distributed user hashCodes, tree bins
are rarely used.  Ideally, under random hashCodes, the
frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because
of resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:
 
0:    0.60653066
 1:    0.30326533
 2:    0.07581633
 3:    0.01263606
 4:    0.00157952
 5:    0.00015795
 6:    0.00001316
 7:    0.00000094
 8:    0.00000006
 more: less than 1 in ten million

若 hashCode 分布良好（hash 计算结果离散好），红黑树很少被用到。理想情况下链表长度符合泊松分布，各长度命中概率依次递减，长度为 8 时概率仅为 0.00000006（小于千万分之一）。Map 通常不会存储这么多数据，所以一般不会发生链表向红黑树的转换。

HashMap 决定元素落桶与对象 hashCode 有关，JDK 无法阻止用户实现自己的哈希算法。若故意使哈希算法不均匀，例如：

java
@Override
public int hashCode() {
    return 1;
}

hashCode 始终返回 1，容易导致 HashMap 链表变长。验证代码：

java
public class HashMapDemo {
 
public static void main(String[] args) {
        HashMap map = new HashMap<HashMapDemo,Integer>(1);
        for (int i = 0; i < 1000; i++) {
            HashMapDemo hashMapDemo1 = new HashMapDemo();
            map.put(hashMapDemo1, null);
        }
        System.out.println("运行结束");
    }
 
@Override
    public int hashCode() {
        return 1;
    }
}

运行时若通过 debug 暂停在 System.out.println("运行结束")，观察 map 内节点已变为 TreeNode 而非通常的 Node，说明内部已转为红黑树。

链表长度超过 8 转为红黑树的设计，主要是防止用户实现不好的哈希算法导致链表过长、查询效率低，此时转红黑树是一种保底策略，保证极端情况下查询效率。

hash 算法正常时链表不会很长，红黑树不会带来明显查询优势，反而增加空间负担。所以选择概率小于千万分之一的长度 8 作为转换默认阈值。

开发中发现 HashMap 或 ConcurrentHashMap 内部出现红黑树结构，通常说明哈希算法出了问题，需检查是否实现了效果不好的 hashCode 方法并改进，以减少冲突。

ConcurrentHashMap 与 Hashtable 的区别

HashMap 线程不安全，ConcurrentHashMap 和 Hashtable 均为线程安全，二者在以下四个角度存在不同。

出现的版本不同

Hashtable 在 JDK 1.0 时存在，JDK 1.2 版本实现 Map 接口，成为集合框架成员。ConcurrentHashMap 在 JDK 1.5 才出现。后出现的类通常是对前面类的优化，二者在实现方式和性能上存在较大不同。

实现线程安全的方式不同

Hashtable 通过 synchronized 关键字实现并发安全，以 clear() 方法为例：

java
public synchronized void clear() {
    Entry<?,?> tab[] = table;
    modCount++;
    for (int index = tab.length; --index >= 0; )
        tab[index] = null;
    count = 0;
}

clear() 被 synchronized 修饰，其他方法如 put、get、size 同样被 synchronized 修饰。Hashtable 因几乎所有方法都被 synchronized 修饰而线程安全。Collections.SynchronizedMap(new HashMap()) 的原理与 Hashtable 类似，也是利用 synchronized。

ConcurrentHashMap 实现原理不同，Java 8 结构示意图：

ConcurrentHashMap 实现线程安全的原理（见第 30 节详述和源码分析）是利用 CAS + synchronized + Node 节点方式，与 Hashtable 完全依赖 synchronized 的方式有很大不同。

性能不同

线程安全实现方式不同导致性能不同。线程数量增加时 Hashtable 性能急剧下降，因为每次修改需锁住整个对象，其他线程期间不能操作，还带来额外上下文切换开销，吞吐量甚至不如单线程。ConcurrentHashMap 上锁时仅对一部分上锁而非全部，多线程吞吐量通常大于单线程，并发效率比 Hashtable 提高很多。

迭代时修改的不同

Hashtable（包括 HashMap）不允许在迭代期间修改内容，否则抛出 ConcurrentModificationException。其原理是检测 modCount 变量，迭代器的 next() 方法：

java
public T next() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    return nextElement();
}

next() 先判断 modCount 是否等于 expectedModCount。expectedModCount 在迭代器生成时产生且不改变，代表当前 Hashtable 被修改的次数；每次调用 addEntry()、remove()、rehash() 等方法都会修改 modCount。若迭代期间修改内容，迭代器在 next() 时发现 modCount 不等于 expectedModCount，抛出 ConcurrentModificationException。

所以 Hashtable 不允许迭代期间修改内容。相反，ConcurrentHashMap 即便迭代期间修改内容，也不会抛出 ConcurrentModificationException。

综上，ConcurrentHashMap 与 Hashtable 虽都线程安全，但在出现版本、实现线程安全方式、性能、迭代时是否支持修改等方面均有较大不同。并发场景使用 ConcurrentHashMap 最合适，Hashtable 已不推荐使用。

CopyOnWriteArrayList 的特点

在 CopyOnWriteArrayList 之前已有 ArrayList、LinkedList，以及线程安全的 Vector 和 Collections.synchronizedList()。Vector 的 size 和 get 方法：

java
public synchronized int size() {
    return elementCount;
}
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
 
return elementData(index);
}

Vector 用 synchronized 保证线程安全，锁粒度大（方法级别），并发量高时易竞争，并发效率较低，与 Hashtable 类似。此外上述 List 迭代期间不允许编辑，否则抛出 ConcurrentModificationException。

从 JDK 1.5 起，Java 并发包提供使用 CopyOnWrite 机制实现的 CopyOnWriteArrayList 作为主要并发 List。CopyOnWrite 并发集合还包括 CopyOnWriteArraySet，其底层用 CopyOnWriteArrayList 实现。

适用场景

  • 读操作尽可能快，写操作慢一些也可以：读操作远多于写操作的场景（如系统级信息只加载或修改很少次数，但被系统内所有模块频繁访问），希望读操作尽可能快，写慢一些没关系。

  • 读多写少：黑名单是最典型场景。搜索网站用户输入关键字搜索，不允许搜索的关键字放在黑名单，黑名单不需要实时更新（如每晚更新一次），用户搜索时检查关键字是否在黑名单。此读多写少场景适合用 CopyOnWrite 集合。

读写规则

  • 读写锁的规则：读写锁思想是"读读共享、其他都互斥"（写写互斥、读写互斥、写读互斥）。读操作不修改原数据，并发读无安全问题；写操作危险，写发生时不允许读操作加入，也不允许第二个写线程加入。

  • 对读写锁规则的升级：CopyOnWriteArrayList 为将读取性能发挥到极致，读取完全不用加锁，且写入不会阻塞读取操作（可边写边读），只有写入与写入之间需要同步。写发生时允许读同时发生，读性能大幅提升。

特点

  • CopyOnWrite 的含义：CopyOnWrite 指容器需要修改时不直接修改当前容器，而是先将当前容器 Copy 出新副本，修改新容器，修改完成后将原容器引用指向新容器，完成整个修改过程。

好处是利用"不变性"原理：容器每次修改都创建新副本，旧容器不可变、线程安全，无需进一步同步。可对 CopyOnWrite 容器并发读而不加锁（当前容器不添加元素也不修改）。所有修改操作（add、set 等）通过创建底层数组新副本实现，体现读写分离思想，读和写使用不同容器。

  • 迭代期间允许修改集合内容：ArrayList 迭代期间修改集合内容会抛出 ConcurrentModificationException。ArrayList 源码 ListItr 的 next 方法中有 checkForComodification 方法：
java
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

该方法检查 modCount 是否等于 expectedModCount。modCount 保存修改次数，每次调用 add、remove、trimToSize 等方法时增加；expectedModCount 是迭代器变量，创建迭代器时初始化并记录当时 modCount。迭代期间若 modCount 与 expectedModCount 不一致，说明集合被修改，抛出异常。

与 ArrayList 不同，CopyOnWriteArrayList 的迭代器迭代时若数组内容被修改，不会抛 ConcurrentModificationException，因为迭代器仍使用旧数组，只是迭代内容可能已过时。演示代码：

java
/**
* 描述： 演示CopyOnWriteArrayList迭代期间可以修改集合的内容
*/
public class CopyOnWriteArrayListDemo {
 
public static void main(String[] args) {
 
CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>(new Integer[]{1, 2, 3});
 
System.out.println(list); //[1, 2, 3]
 
//Get iterator 1
        Iterator<Integer> itr1 = list.iterator();
 
//Add one element and verify list is updated
        list.add(4);
 
System.out.println(list); //[1, 2, 3, 4]
 
//Get iterator 2
        Iterator<Integer> itr2 = list.iterator();
 
System.out.println("====Verify Iterator 1 content====");
 
itr1.forEachRemaining(System.out::println); //1,2,3
 
System.out.println("====Verify Iterator 2 content====");
 
itr2.forEachRemaining(System.out::println); //1,2,3,4
 
}
 
}

代码创建初始值为 [1, 2, 3] 的 CopyOnWriteArrayList，创建 itr1 迭代器后调用 list.add(4) 添加元素，List 变为 [1, 2, 3, 4]，再创建 itr2 迭代器。运行结果：

java
[1, 2, 3]
[1, 2, 3, 4]
====Verify Iterator 1 content====
1
2
3
====Verify Iterator 2 content====
1
2
3
4

两个迭代器打印内容不同：itr1 为 [1, 2, 3]，itr2 为 [1, 2, 3, 4]。虽然打印时机都在第四个元素添加后，但创建时机不同。迭代器 1 创建时 List 只有三个元素，后续任何修改对它无感知。

结论：CopyOnWriteArrayList 迭代器一旦建立后，向原对象新增元素，迭代器既不会显示变更，也不会报错，与 ArrayList 有很大区别。

缺点

以下缺点不仅针对 CopyOnWriteArrayList，也适用于其他 CopyOnWrite 容器：

  • 内存占用问题：写时复制机制使写操作时内存同时驻扎两个对象的内存，占用额外内存空间。

  • 在元素较多或复杂的情况下，复制的开销很大：复制不仅占用双倍内存，还消耗 CPU 等资源，降低整体性能。

  • 数据一致性问题：修改先作用于副本，此次修改对其它线程并非实时可见，只有修改完成后才体现。若希望写入数据马上被其他线程看到，CopyOnWrite 容器不适用。

源码分析

  • 数据结构
java
/** 可重入锁对象 */
final transient ReentrantLock lock = new ReentrantLock();
 
/** CopyOnWriteArrayList底层由数组实现，volatile修饰，保证数组的可见性 */
private transient volatile Object[] array;
 
/**
* 得到数组
*/
final Object[] getArray() {
    return array;
}
 
/**
* 设置数组
*/
final void setArray(Object[] a) {
    array = a;
}
 
/**
* 初始化CopyOnWriteArrayList相当于初始化数组
*/
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

类中有 ReentrantLock 锁，保证修改操作线程安全。命名为 array 的 Object[] 数组被 volatile 修饰，保证数组可见性，是存储元素的数组。从 getArray()、setArray() 及构造方法可见 CopyOnWriteArrayList 底层用数组实现。

  • add 方法
java
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;
 
// 将volatile Object[] array 的指向替换成新数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

add 方法流程：先用 ReentrantLock 加锁；获取原数组长度和元素（getArray 得到 elements 并保存 length）；用 Arrays.copyOf 复制新数组；把新元素添加到新数组；用 setArray(newElements) 将 volatile Object[] array 指向替换为新数组；最后在 finally 中解锁。

总结：添加时上锁，复制新数组，增加操作在新数组上完成，将 array 指向新数组，最后解锁。

上述步骤实现 CopyOnWrite 思想：写操作在容器拷贝上进行，读取数据时不锁 list。拷贝操作过程中有新的读线程进来，读到的还是旧数据（此时引用尚未更改）。

读操作相关代码（get 两个重载和 getArray）：

java
public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

get 相关操作不加锁，保证读取高速。

  • 迭代器 COWIterator 类

迭代器有两个重要属性：Object[] snapshot 和 int cursor。snapshot 代表数组快照（创建迭代器时刻的数组情况），cursor 是迭代器游标。构造方法：

java
private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    snapshot = elements;
}

迭代器构建时把当时 elements 赋值给 snapshot，之后所有操作基于 snapshot 数组：

java
public E next() {
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}

next 方法返回 snapshot 对象，后续原数组被修改，snapshot 既不感知也不受影响，执行迭代操作无需加锁，也不会抛异常。迭代器返回结果与创建迭代器时内容一致。

CopyOnWriteArrayList 要点总结：诞生前的 Vector 和 Collections.synchronizedList() 特点；适用场景、读写规则；两个特点（写时复制、迭代期间允许修改集合内容）；三个缺点（内存占用、元素多或复杂时复制开销大、数据一致性）；重要源码解析。

阻塞队列

阻塞队列的作用

阻塞队列即 BlockingQueue，是一个接口：

java
public interface BlockingQueue<E> extends Queue<E>{...}

BlockingQueue 继承 Queue 接口，是队列的一种。Queue 和 BlockingQueue 都在 Java 5 中加入。

BlockingQueue 线程安全，可用线程安全队列优雅解决业务自身的线程安全问题。生产者和消费者模式中，生产者往队列添加元素，消费者从队列取出元素，如图所示：

图中左侧三个生产者线程把生产结果放到中间阻塞队列，右侧三个消费者从队列取出内容处理。因阻塞队列线程安全，生产者和消费者都可多线程，不会发生线程安全问题。

队列可安全地从一线程向另一线程传递数据，生产者和消费者直接使用线程安全队列即可，无需自己考虑更多线程安全问题。考虑锁等线程安全问题的重任从开发方转移到"队列"上，降低开发难度和工作量。

队列还能起隔离作用。如银行转账程序，生产者线程无需关心转账逻辑，只需把转账任务（账户和金额等）放入队列；银行类从队列取出待执行任务，通过自身方法完成转账。这实现具体任务与执行任务类之间的解耦，任务放在阻塞队列中，放任务的线程无法直接访问银行转账实现对象，实现隔离、提高安全性。

主要并发队列关系图

Java 提供的线程安全队列（并发队列）分为阻塞队列和非阻塞队列两大类。

阻塞队列典型例子是 BlockingQueue 接口的实现类，主要有 6 种：ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、DelayQueue、PriorityBlockingQueue 和 LinkedTransferQueue，各自特点见第 36 节。

非阻塞并发队列典型例子是 ConcurrentLinkedQueue，不会让线程阻塞，利用 CAS 保证线程安全。

可根据需要自由选取阻塞队列或非阻塞队列满足业务需求。

与 Queue 关系紧密的 Deque 接口继承自 Queue：

java
public interface Deque<E> extends Queue<E> {//...}

Deque（双端队列，double-ended-queue 缩写）从头和尾都能添加和删除元素；普通 Queue 只能一端进、另一端出。这是 Deque 与 Queue 的不同，其他性质类似。

阻塞队列的特点

阻塞队列区别于其他类型队列的最主要特点是"阻塞"。阻塞功能使生产者和消费者两端能力平衡，任一端速度过快时，阻塞队列会将其速度降下来。实现阻塞最重要的两个方法是 take 方法和 put 方法。

take 方法

take 方法获取并移除队列头结点，队列有数据时可正常移除；执行 take 时队列无数据则阻塞，直到队列有数据；队列有数据后立刻解除阻塞并取到数据。过程如图所示：

put 方法

put 方法插入元素时，若队列未满则正常插入；若队列已满则无法继续插入，阻塞直到队列有空闲空间；后续队列有空闲空间（如消费者消费一个元素）则解除阻塞，把数据添加到队列。过程如图所示：

以上阻塞和解除阻塞均由 BlockingQueue 完成，无需自己处理。

是否有界（容量有多大）

阻塞队列容量分为有界和无界两种。

无界队列可容纳非常多元素，如 LinkedBlockingQueue 上限是 Integer.MAX_VALUE（约 2 的 31 次方），可近似认为无限容量，几乎无法装满。

有界队列如 ArrayBlockingQueue 容量满了不会扩容，一旦满了就无法再放数据。

阻塞队列要点：作用（线程安全、解耦、隔离）、并发队列分类（阻塞/非阻塞，阻塞队列有 6 种常见实现）、特点（take 方法、put 方法、是否有界）。

阻塞队列的常用方法

BlockingQueue 最常用的与添加、删除相关的 8 个方法可分为三组，每组都与添加、移除元素相关。三组方法功能类似，区别仅在特殊情况：队列满无法添加或队列空无法移除时，不同组方法处理方式不同：

  • 抛出异常：add、remove、element
  • 返回结果但不抛出异常：offer、poll、peek
  • 阻塞：put、take

第一组：add、remove、element

add 方法

add 往队列添加一个元素，队列满时抛异常提示队列已满。示例：

java
private static void addTest() {
    BlockingQueue<Integer> blockingQueue = new                     ArrayBlockingQueue<Integer>(2);
    blockingQueue.add(1);
    blockingQueue.add(1);
    blockingQueue.add(1);
}

创建容量为 2 的 BlockingQueue 放 3 个值，添加第三个值时得到异常：

java
Exception in thread "main" java.lang.IllegalStateException:Queue full

remove 方法

remove 删除元素，队列为空时无元素可删，抛出异常。示例：

java
private static void removeTest() {
    ArrayBlockingQueue<Integer> blockingQueue = new     ArrayBlockingQueue<Integer>(2);
    blockingQueue.add(1);
    blockingQueue.add(1);
    blockingQueue.remove();
    blockingQueue.remove();
    blockingQueue.remove();
}

往容量 2 的队列放入 2 个元素，删除 3 个。删除前两个正常，删除第三个时队列已空，抛异常：

java
Exception in thread "main" java.util.NoSuchElementException

element 方法

element 返回队列头部节点但不删除。操作空队列时抛 NoSuchElementException（与 remove 相同）。示例：

java
private static void elementTest() {
    ArrayBlockingQueue<Integer> blockingQueue = new     ArrayBlockingQueue<Integer>(2);
    blockingQueue.element();
}

新建容量 2 的 ArrayBlockingQueue 直接调用 element，因队列为空，得到异常：

java
Exception in thread "main" java.util.NoSuchElementException

第二组：offer、poll、peek

第二组比第一组友好，当队列满无法添加或队列空无法删除时给出提示而非抛异常。

offer 方法

offer 插入元素，用返回值提示是否成功。成功返回 true；队列满时继续调用不抛异常，返回 false。示例：

java
private static void offerTest() {
    ArrayBlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<Integer>(2);
    System.out.println(blockingQueue.offer(1));
    System.out.println(blockingQueue.offer(1));
    System.out.println(blockingQueue.offer(1));
}

容量 2 的队列调用三次 offer，运行结果：

java
true
true
false

前两次添加成功，第三次超过最大容量返回 false。

poll 方法

poll 对应第一组 remove，移除并返回头节点；队列空时返回 null 提示。因无法区分返回 null 是提示还是元素，不允许往队列插入 null。示例：

java
private static void pollTest() {
    ArrayBlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<Integer>(3);
    blockingQueue.offer(1);
    blockingQueue.offer(2);
    blockingQueue.offer(3);
    System.out.println(blockingQueue.poll());
    System.out.println(blockingQueue.poll());
    System.out.println(blockingQueue.poll());
    System.out.println(blockingQueue.poll());
}

容量 3 的队列放入 3 个元素，四次调用 poll，运行结果：

java
1
2
3
null

前三次成功并返回 1、2、3（先进先出），第四次返回 null 代表无元素可移除。

peek 方法

peek 对应第一组 element，返回头元素但不删除；队列空时返回 null。示例：

java
private static void peekTest() {
    ArrayBlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<Integer>(2);
    System.out.println(blockingQueue.peek());
}

运行结果：

java
null

新建空队列直接调用 peek，返回 null。

带超时时间的 offer 和 poll

offer 和 poll 都有带超时时间的重载方法：

java
offer(E e, long timeout, TimeUnit unit)

三个参数为元素、超时时长、时间单位。通常插入成功返回 true；队列满导致插入不成功时，等待指定超时时间，超时仍未插入成功则返回 false。

java
poll(long timeout, TimeUnit unit)

带时间参数 poll 与 offer 类似：能移除则立即返回节点内容；队列空则等待指定时间，超时仍无元素可移除返回 null。

第三组：put、take

put 和 take 是阻塞队列最大特色的方法（见第 34 节）。

put 方法

put 插入元素，队列未满时正常插入；队列已满时既不立即返回 false 也不抛异常，而是让插入线程陷入阻塞，直到队列有空闲空间，此时队列解除之前线程的阻塞，并把元素添加进去。

take 方法

take 获取并移除头结点，队列有数据时正常取出并删除；执行 take 时队列无数据则阻塞，直到队列有数据；队列有数据后立刻解除阻塞并取到数据。

总结

三组方法特点：

  • 第一组（add、remove、element）：无法正常执行时抛异常。
  • 第二组（offer、poll、peek）：无法正常执行时不抛异常，用返回值提示运行失败。
  • 第三组（put、take）：遇到特殊情况时让线程陷入阻塞，等到可运行再继续。

8 种方法总结如下表：

此表可清晰理清 8 个方法间的关系。

常见的阻塞队列

BlockingQueue 接口的实现类都放在 J.U.C 包中。常见实现类包括 ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityBlockingQueue、DelayQueue。

ArrayBlockingQueue

ArrayBlockingQueue 是最典型的有界队列，内部用数组存储元素，利用 ReentrantLock 实现线程安全。

创建时需指定容量，之后不可扩容，构造函数可指定是否公平：

java
ArrayBlockingQueue(int capacity, boolean fair)

第一个参数是容量，第二个参数是是否公平。与 ReentrantLock 一样，ArrayBlockingQueue 设为非公平时存在插队可能；设为公平时等待最长时间的线程优先处理，其他线程不允许插队，但公平策略带来一定性能损耗（非公平吞吐量通常高于公平）。

LinkedBlockingQueue

内部用链表实现的 BlockingQueue。不指定初始容量时默认容量为整型最大值 Integer.MAX_VALUE，因数值非常大、通常不可能放入这么多数据，LinkedBlockingQueue 也被称为无界队列，代表几乎没有界限。

SynchronousQueue

SynchronousQueue 容量为 0，没有地方暂存元素，每次取数据都要先阻塞直到有数据被放入；每次放数据也会阻塞直到有消费者来取。

SynchronousQueue 的容量是 0 而非 1，因为它不需要持有元素，只做直接传递（direct handoff）。每次传递时把元素直接从生产者传给消费者，无需存储，运用得当效率很高。

容量为 0 使 SynchronousQueue 的许多方法实现特殊。peek 方法永远返回 null：

java
public E peek() {
    return null;
}

peek 含义是取出头结点，但 SynchronousQueue 容量为 0，连头结点都没有，peek 无意义，始终返回 null。同理 element 始终抛 NoSuchElementException。

size 方法始终返回 0：

java
public int size() {
    return 0;
}

isEmpty 方法始终返回 true：

java
public boolean isEmpty() {
    return true;
}

因它始终都是空的。

PriorityBlockingQueue

ArrayBlockingQueue 和 LinkedBlockingQueue 采用先进先出顺序排序，需要自定义排序时使用 PriorityBlockingQueue。

PriorityBlockingQueue 是支持优先级的无界阻塞队列，可通过自定义类实现 compareTo() 指定排序规则，或初始化时通过构造器参数 Comparator 指定。插入队列的对象必须是可比较大小的（Comparable），否则抛 ClassCastException。

take 方法在队列为空时阻塞；因是无界队列且自动扩容，队列永远不会满，put 方法永不阻塞，添加操作始终成功。因此它的成员变量只有一个 Condition：

java
private final Condition notEmpty;

这与 ArrayBlockingQueue 拥有两个 Condition（notEmpty 和 notFull）形成对比。PriorityBlockingQueue 不需要 notFull，因为它永远不会满。

DelayQueue

DelayQueue 具有"延迟"功能，可设定队列中任务延迟多久后执行（如 10 秒后执行），大量用于"30 分钟后未付款自动取消订单"等延迟执行场景。

它是无界队列，放入的元素必须实现 Delayed 接口，Delayed 接口继承 Comparable，自然拥有比较和排序能力：

java
public interface Delayed extends Comparable<Delayed> {
    long getDelay(TimeUnit unit);
}

Delayed 接口继承自 Comparable，有一个需实现的方法 getDelay，返回"还剩下多长的延迟时间才会被执行"，若返回 0 或负数代表任务已过期。

元素根据延迟时间长短被放到队列不同位置，越靠近队列头代表越早过期。

DelayQueue 内部使用 PriorityQueue 能力排序而非从头编写，可复用已有功能，减少开发量，避免"重复造轮子"。

ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、PriorityBlockingQueue、DelayQueue 这些常见阻塞队列的特点已逐一介绍。

阻塞与非阻塞队列的并发安全原理

以 ArrayBlockingQueue 为例分析阻塞队列线程安全原理，再分析非阻塞队列的并发安全原理。

ArrayBlockingQueue 源码分析

ArrayBlockingQueue 有几个重要属性：

java
final Object[] items;
int takeIndex;
int putIndex;
int count;
  • Object[] items：核心的用于存储元素的数组。
  • takeIndex、putIndex：标明下一次读取和写入位置的两个变量。
  • count：计数，记录队列中的元素个数。

另外还有三个变量：

java
final ReentrantLock lock;
private final Condition notEmpty;
private final Condition notFull;
  • lock：一个 ReentrantLock。
  • notEmpty、notFull：两个由 ReentrantLock 产生的 Condition。

这三个变量是实现线程安全最核心的工具。ArrayBlockingQueue 利用 ReentrantLock 和两个 Condition 实现并发安全，真正执行读写操作前需先获取锁。

分析最重要的 put 方法：

java
public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
        notFull.await();
        enqueue(e);
    } finally {
        lock.unlock();
    }
}

put 方法先用 checkNotNull 检查插入元素是否 null；非 null 后用 lock.lockInterruptibly() 上锁，该方法在获取锁的同时可响应中断（见第 23 节），这正是阻塞队列调用 put 方法在尝试获取锁但未拿到锁期间可响应中断的底层原因。

随后是经典 try-finally 代码块，finally 中解锁，try 中有 while 循环检查队列是否已满（count 是否等于数组长度）。已满则等待，有空余后才调用 enqueue 让元素进入队列，最后 unlock 解锁。

该代码与第 5 节用 Condition 实现生产者/消费者模式时写的 put 方法几乎一致：

java
public void put(Object o) throws InterruptedException {
    lock.lock();
    try {
        while (queue.size() == max) {
        notFull.await();
    }
    queue.add(o);
    notEmpty.signalAll();
    } finally {
        lock.unlock();
    }
}

两个 put 方法几乎一模一样。用 Condition 实现生产者/消费者模式，本质上就是实现了简易版 BlockingQueue。对比两个 put 方法实现可加深对 Condition 的理解。

与 ArrayBlockingQueue 类似，其他阻塞队列（LinkedBlockingQueue、PriorityBlockingQueue、DelayQueue、DelayedWorkQueue 等）内部也利用 ReentrantLock 保证线程安全，只是细节有差异。例如 LinkedBlockingQueue 内部有两把锁分别锁队列头和尾，比共用一把锁效率更高，但总体思想类似。

非阻塞队列ConcurrentLinkedQueue

ConcurrentLinkedQueue 使用链表作为数据结构，关键方法 offer 的源码：

java
public boolean offer(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);
 
for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {
            // p is last node
            if (p.casNext(null, newNode)) {
                // Successful CAS is the linearization point
                // for e to become an element of this queue,
                // and for newNode to become "live".
                if (p != t) // hop two nodes at a time
                    casTail(t, newNode);  // Failure is OK.
                return true;
            }
            // Lost CAS race to another thread; re-read next
        }
        else if (p == q)
            // We have fallen off list.  If tail is unchanged, it
            // will also be off-list, in which case we need to
            // jump to head, from which all live nodes are always
            // reachable.  Else the new tail is a better bet.
            p = (t != (t = tail)) ? t : head;
        else
            // Check for tail updates after two hops.
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

从整体代码结构看，检查空判断后是一个大的 for 循环（明显的死循环）。循环中有个关键方法 p.casNext，正是利用 CAS 操作；死循环配合 CAS 是典型的乐观锁思想。p.casNext 方法实现：

java
boolean casNext(Node<E> cmp, Node<E> val) {
    return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}

这里运用 UNSAFE.compareAndSwapObject 完成 CAS 操作，compareAndSwapObject 是 native 方法，最终利用 CPU 的 CAS 指令保证不可中断。

非阻塞队列 ConcurrentLinkedQueue 使用 CAS 非阻塞算法 + 不停重试实现线程安全，适合不需要阻塞功能且并发不是特别剧烈的场景。

总结

  • 阻塞队列最主要是利用 ReentrantLock 及它的 Condition 实现并发安全。
  • 非阻塞队列利用 CAS 方法实现线程安全。

参考：https://javadoop.com/post/java-concurrent-queue

阻塞队列的选择

线程池在选择阻塞队列上已率先做出表率。不同种类的线程池根据自身特点选择适合自己的阻塞队列，可借鉴其经验总结选取规则。

线程池对于阻塞队列的选择

表格左侧是线程池，右侧为对应阻塞队列，5 种线程池只对应 3 种阻塞队列，逐一介绍：

  • FixedThreadPool（SingleThreadExecutor 同理）选取 LinkedBlockingQueue：LinkedBlockingQueue 不同于 ArrayBlockingQueue（容量有限），其链表长度默认可无限延长。FixedThreadPool 线程数固定，任务激增时无法增加线程处理 Task，需要像 LinkedBlockingQueue 这样无容量上限的 Queue 存储未处理 Task。若所有 corePoolSize 线程都在忙，新任务进入阻塞队列等待；队列无容量上限、永不填满，保证 FixedThreadPool 和 SingleThreadExecutor 不拒绝新任务提交、不丢失数据。

  • CachedThreadPool 选取 SynchronousQueue：为避免新任务被拒绝，CachedThreadPool 选择无限制的 maximumPoolSize，线程最大数量无限、线程数不受限制，因此不需要额外空间存储 Task，每个任务都可通过新建线程处理。SynchronousQueue 直接把任务交给线程、无需另外保存，效率更高，故 CachedThreadPool 使用 SynchronousQueue。

  • ScheduledThreadPool（SingleThreadScheduledExecutor 同理）选取延迟队列：ScheduledThreadPool 使用 DelayedWorkQueue。延迟队列不是先进先出，而是按延迟时间长短排序，下一个即将执行的任务排到最前面。

例如队列中先放延迟 10 分钟执行的任务，再放延迟 10 秒执行的任务。非延迟队列按先进先出规则，延迟 10 分钟的任务先放置、在最前面；但使用阻塞队列时按延迟时间长短排放位置，第二个放置的延迟 10 秒任务反而排在延迟 10 分钟任务前面（其执行时间更早）。

选择延迟队列的原因是 ScheduledThreadPool 处理基于时间执行的 Task，而延迟队列能把 Task 按执行时间先后排序，正是所需功能。

ArrayBlockingQueue

除线程池选择的 3 种阻塞队列外，ArrayBlockingQueue 也常用于手动创建的线程池。

ArrayBlockingQueue 内部用数组实现，新建对象时要求传入容量值，后期不能扩容，最大特点是容量有限且固定。使用 ArrayBlockingQueue 且设置合理最大线程数的线程池，任务队列放满后若线程数也达最大值，线程池按规则拒绝新任务提交，不会无限增加任务或线程数导致内存不足，有效防止资源耗尽。

归纳

通常可从 5 个角度考虑选择合适阻塞队列：

  • 功能：是否需要阻塞队列排序，如优先级排序、延迟执行等。有需要则选择类似 PriorityBlockingQueue 之类有排序能力的阻塞队列。

  • 容量：是否有存储要求，还是只需"直接传递"。前文几种队列中：ArrayBlockingQueue 容量固定；LinkedBlockingQueue 默认容量无限；SynchronousQueue 没有任何容量；DelayQueue 容量固定为 Integer.MAX_VALUE。不同队列容量千差万别，需根据任务数量推算出合适容量从而选取合适 BlockingQueue。

  • 能否扩容：业务可能有高峰期、低谷期，初始时不一定能准确估计队列大小。若需动态扩容，不能选 ArrayBlockingQueue（容量创建时确定、无法扩容）；PriorityBlockingQueue 即使指定初始容量，后续需要也可自动扩容。

  • 内存结构：ArrayBlockingQueue 内部结构是"数组"，LinkedBlockingQueue 内部用链表实现。ArrayBlockingQueue 没有链表所需的"节点"，空间利用率更高。对性能有要求可从内存结构角度考虑。

  • 性能：LinkedBlockingQueue 拥有两把锁、操作粒度更细，并发程度高时相对只有一把锁的 ArrayBlockingQueue 性能更好。SynchronousQueue 性能往往优于其他实现（只需"直接传递"、无需存储），需要直接传递场景可优先考虑。

选取规则归纳：回顾线程池对阻塞队列的选取规则，看到 ArrayBlockingQueue 特点，通常从功能、容量、能否扩容、内存结构、性能这 5 个角度结合业务选取最适合的阻塞队列。

Java 21 并发容器新内容

SequencedCollection / SequencedMap（JEP 431）

Java 21 引入 SequencedCollection（有序集合）与 SequencedMap（有序 Map）接口，统一了支持头尾双向访问的集合 API：

java
// 旧版：反向遍历需手动转换
List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (int i = list.size() - 1; i >= 0; i--) { /* ... */ }
 
// Java 21：直接调用 reversed()
SequencedCollection<String> seq = list;
seq.getFirst();   // "a"
seq.getLast();    // "c"
seq.reversed();   // [c, b, a]

ConcurrentHashMap 虽然不是 SequencedMap，但 ConcurrentSkipListMap 实现了 NavigableMap/SequencedMap，支持有序并发访问。

并发容器 vs 虚拟线程

Java 21 中，虚拟线程的高并发 IO 场景下，共享可变状态仍须使用并发容器；但如果任务无共享状态（如纯 IO 请求），可减少对容器的依赖。

场景推荐方案
高频读写共享 MapConcurrentHashMap
高频追加读多写少CopyOnWriteArrayList
高并发有序 KVConcurrentSkipListMap（支持 SequencedMap）
任务队列虚拟线程 + 无队列直接调度

版本差异(旧版 → Java 21)

特性旧版(Java 7/8)Java 21
有序集合 API分散，无统一接口SequencedCollection/SequencedMap（JEP 431）
ConcurrentHashMapJDK 8 起 CAS + synchronized 桶不变，仍是首选并发 Map
阻塞队列7 种实现不变；新增队列场景可配合虚拟线程
头尾访问需手动转换getFirst/getLast/reversed 直接支持