前置阅读：
- 数据结构等算法概念
- 树
- 堆排序
- 锁相关概念：
- 锁概念
- 锁实现
队列
Queue 与 Deque 的区别
Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则
Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Deque 是双端队列，在队列的两端均可以插入或删除元素。
Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：
Queue
java.util包中的Queue实现默认非线程安全
java.util.concurrent包中的Queue实现均为线程安全
| 实现类 | 数据结构 | 边界 | 锁机制 | 吞吐量 | 适用场景 |
|---|---|---|---|---|---|
| ConcurrentLinkedQueue | 链表 | 无界 | 完全无锁（CAS） | 最高 | 高并发写入 |
| LinkedBlockingQueue | 链表 | 可选界，默认是Integer.MAX_VALUE | 双锁分离 | 高 | 通用阻塞队列 |
| ArrayBlockingQueue | 数组 | 有界 | 单锁+条件变量 | 中 | 固定容量场景 |
| SynchronousQueue | 无缓冲 | 特殊 | 无存储 | 可变 | 直接传递模式 |
| PriorityBlockingQueue | 堆 | 无界 | 单锁 | 中 | 优先级任务调度 |
实际开发中应根据具体场景选择：
- 高吞吐读场景（高并发非阻塞访问） → ConcurrentLinkedQueue
- 资源池管理（生产者-消费者模型） → LinkedBlockingQueue
- 定时任务调度 → DelayQueue
- 简单同步需求 → 同步包装队列
BlockingQueue（接口）
BlockingQueue 通常用于一个线程生产对象，而另外一个线程消费这些对象的场景
一个线程将会持续生产新对象并将其插入到队列之中，直到队列达到它所能容纳的临界点（有限的）。
- 如果该阻塞队列到达了其临界点，负责生产的线程将会在往里边插入新对象时发生阻塞。它会一直处于阻塞之中，直到负责消费的线程从队列中拿走一个对象。
- 负责消费的线程将会一直从该阻塞队列中拿出对象。如果消费线程尝试去从一个空的队列中提取对象的话，这个消费线程将会处于阻塞之中，直到一个生产线程把一个对象丢进队列。
四组不同的行为方式解释:
- 抛异常: 如果试图的操作无法立即执行，抛一个异常。
- 特定值: 如果试图的操作无法立即执行，返回一个特定的值(常常是 true / false)。
- 阻塞: 如果试图的操作无法立即执行，该方法调用将会发生阻塞，直到能够执行。
- 超时: 如果试图的操作无法立即执行，该方法调用将会发生阻塞，直到能够执行，但等待时间不会超过给定值。返回一个特定值以告知该操作是否成功(典型的是 true / false)。
ArrayBlockingQueue（类）
ArrayBlockingQueue 类实现了 BlockingQueue 接口
ArrayBlockingQueue 基于数组实现
ArrayBlockingQueue内部以FIFO(先进先出) 才的顺序对元素进行存储。
队列中的头元素在所有元素之中是放入时间最久的那个，而尾元素则是最短的那个
ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁
LinkedBlockingQueue（类）
LinkedBlockingQueue 类实现了 BlockingQueue 接口。
内部以一个链式结构(链接节点)对其元素进行存储。
LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。
DelayQueue（类）
DelayQueue 实现了 BlockingQueue 接口。
对元素进行持有直到一个特定的延迟到期。注入其中的元素必须实现 java.util.concurrent.Delayed 接口
public interface Delayed extends Comparable<Delayed< {public long getDelay(TimeUnit timeUnit);
}
PriorityQueue（类）
其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
要点：
- PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
- PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
- PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境
- PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
- 数组的第一个元素是堆顶，也就是优先级最高的元素。每次插入一个元素时，PriorityQueue会先将元素添加到数组末尾，然后通过上浮操作来维护小顶堆的性质。每次删除堆顶元素时，PriorityQueue会先将数组末尾元素移动到堆顶，然后通过下沉操作来维护小顶堆的性质
大/小顶堆
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
PriorityBlockingQueue（类）
线程安全实现
具有优先级的阻塞队列
PriorityBlockingQueue 类实现了 BlockingQueue 接口。
使用了和类 java.util.PriorityQueue 一样的排序规则
核心机制：
- 使用 ReentrantLock 保证操作原子性
- 基于 Condition 实现阻塞等待
- 动态扩容策略（与PriorityQueue类似
SynchronousQueue（同步队列）
SynchronousQueue 类实现了 BlockingQueue 接口。
特殊的队列，它的内部同时只能够容纳单个元素
如果该队列已有一元素的话，试图向队列中插入一个新元素的线程将会阻塞，直到另一个线程将该元素从队列中抽走。
如果该队列为空，试图向队列中抽取一个元素的线程将会阻塞，直到另一个线程向队列中插入了一条新的元素。
ConcurrentLinkedQueue
一个基于链接节点的无界线程安全队列。
此队列按照 FIFO(先进先出)原则对元素进行排序。
队列的头部是队列中时间最长的元素。
队列的尾部 是队列中时间最短的元素。
新的元素插入到队列的尾部，队列获取操作从队列头部获得元素
两者更新触发时机为：
- tail更新触发时机：当tail指向的节点的下一个节点不为null的时候，会执行定位队列真正的队尾节点的操作，找到队尾节点后完成插入之后才会通过casTail进行tail更新；当tail指向的节点的下一个节点为null的时候，只插入节点不更新tail。
- head更新触发时机：当head指向的节点的item域为null的时候，会执行定位队列真正的队头节点的操作，找到队头节点后完成删除之后才会通过updateHead进行head更新；当head指向的节点的item域不为null的时候，只删除节点不更新head。
通过无锁来做到了更高的并发量，是个高性能的队列（该队列是基于链接节点的无界线程安全队列，采用CAS操作实现非阻塞算法。）
ConcurrentLinkedQueue的HOPS(延迟更新的策略)的设计?
HOPS（延迟更新机制） 是 ConcurrentLinkedQueue 实现高性能无锁队列的核心优化策略，通过减少 CAS 操作次数来提升并发性能。其核心设计体现在 tail 节点的更新策略上
调整策略依据：
- 写多读少场景 → 增大HOPS值减少CAS竞争
- 读多写少场景 → 减小HOPS值加快遍历速度
HOPS策略设计启示
- 空间换时间思想：允许数据结构短期不一致换取长期高性能
- 概率化优化：通过统计学规律而非绝对正确性保证性能
- 自适应调节：参数(HOPS值)可根据运行时状况动态调整
线程安全性保障
| 实现类型 | 典型类 | 同步策略 | 适用场景 |
|---|---|---|---|
| 阻塞队列 | ArrayBlockingQueue | ReentrantLock + Condition（单锁控制） | 固定容量生产消费模型 |
| 无锁队列 | ConcurrentLinkedQueue | HOPS + CAS 自旋 | 高吞吐非阻塞访问 |
| 双锁队列 | LinkedBlockingQueue | putLock/takeLock 分离（双锁分离） | 无界/有界缓冲队列 |
| 优先级阻塞队列 | PriorityBlockingQueue | ReentrantLock + 堆调整 | 带优先级的任务调度 |
Deque
BlockingDeque（接口）
BlockingDeque 接口继承自 BlockingQueue 接口
表示一个线程安放入和提取实例的双端队列，在不能够插入元素时，它将阻塞住试图插入元素的线程；在不能够抽取元素时，它将阻塞住试图抽取的线程。
双端队列是一个你可以从任意一端插入或者抽取元素的队列。
线程既是一个队列的生产者又是这个队列的消费者的时候可以使用到 BlockingDeque
如果生产者线程需要在队列的两端都可以插入数据，消费者线程需要在队列的两端都可以移除数据，这个时候也可以使用 BlockingDeque。
如果双端队列已满，插入线程将被阻塞，直到一个移除线程从该队列中移出了一个元素。如果双端队列为空，移除线程将被阻塞，直到一个插入线程向该队列插入了一个新元素。
LinkedBlockingDeque
LinkedBlockingDeque 类实现了 BlockingDeque 接口。
LinkedBlockingDeque 是一个双端队列，在它为空的时候，一个试图从中抽取数据的线程将会阻塞，无论该线程是试图从哪一端抽取数据。
ConcurrentLinkedDeque
是双向链表实现的无界队列，该队列同时支持FIFO和FILO两种操作方式。
什么叫CopyOnWrite
当我们往一个容器添加元素的时候，不直接往容器中添加，而是先复制出一个新的容器，然后在新的容器里添加元素，添加完之后，再将原容器的引用指向新的容器。
多个线程在读的时候，不需要加锁，因为当前容器不会添加任何元素。
写时复制的思想来通过延时更新的策略实现数据的最终一致性，并且能够保证读线程间不阻塞。当然，这要牺牲数据的实时性。
List
CopyOnWriteArrayList
ArrayList 的一个线程安全的变体，其中所有可变操作(add、set 等等)都是通过对底层数组进行一次新的复制来实现的
CopyOnWriteArrayList实现了List接口，List接口定义了对列表的基本操作；
同时实现了RandomAccess接口，表示可以随机访问(数组具有随机访问的特性)；
同时实现了Cloneable接口，表示可克隆；
同时也实现了Serializable接口，表示可被序列化。
属性中有一个可重入锁ReentrantLock/synchronized ，用来保证线程安全访问
if (JDK < 11) {// 注意ReentrantLock特性
} else {// 按synchronized机制理解即可
}还有一个Object类型的数组，用来存放具体的元素。
使用到了反射机制和CAS来保证原子性的修改lock域
addIfAbsent方法：该函数用于添加元素(如果数组中不存在，则添加；否则，不添加，直接返回)，可以保证多线程环境下不会重复添加元素。
线程安全保证
CopyOnWriteArrayList 通过写时复制和不可变快照机制实现线程安全
CopyOnWriteArrayList通过牺牲写性能和内存效率，换取了极佳的读并发能力，适合以遍历为主的黑名单管理、事件广播等特定场景。在使用时需要特别注意其迭代器快照隔离特性和写放大效应带来的成本
三要素保障
| 安全维度 | 实现方式 |
|---|---|
| 可见性 | volatile修饰数组引用，保证修改立即可见 |
| 原子性 | 写操作使用ReentrantLock/synchronized保证单线程修改 |
| 有序性 | 通过volatile写建立happen-before关系 |
CopyOnWriteArrayList为什么并发安全且性能比Vector好
Vector是增删改查方法都加了synchronized 来保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，
而CopyOnWriteArrayList只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector。
| 维度 | Vector | CopyOnWriteArrayList |
|---|---|---|
| 锁粒度 | 方法级 synchronized 锁 | 写操作使用独占锁，读操作无锁 |
| 并发策略 | 读写完全互斥 | 读写分离，读读并行 |
| 锁竞争 | 高频率操作时容易产生激烈竞争 | 仅在写操作时存在短暂锁竞争 |
一致性级别对比
| 维度 | Vector | CopyOnWriteArrayList |
|---|---|---|
| 一致性类型 | 强一致性 | 最终一致性 |
| 读操作可见性 | 总是最新数据 | 可能看到历史快照 |
| 写操作影响范围 | 全局立即可见 | 新读请求才能看到更新 |
| 典型代价 | 锁竞争开销 | 内存复制开销 |
示例如下
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(Arrays.asList("A", "B"));// 线程1（写操作）
new Thread(() -> {list.add("C");list.set(0, "A1");
}).start();// 线程2（读操作）
new Thread(() -> {// 可能读取到以下任意一种状态：// Case1: ["A", "B"] (写操作未开始)// Case2: ["A", "B", "C"] (add完成但set未执行)// Case3: ["A1", "B", "C"] (全部写操作完成)System.out.println(list);
}).start();Set
CopyOnWriteArraySet
对其所有操作使用内部CopyOnWriteArrayList的Set。
其所有操作转发至CopyOnWriteArayList来进行操作，能够保证线程安全。
在add时，会调用addIfAbsent，由于每次add时都要进行数组遍历，因此性能会略低于CopyOnWriteArrayList。
ConcurrentSkipListSet
跳表（SkipList）是什么
跳表是基于链表实现的有序列表，跳表通过维护一个多层级的链表实现了快速查询效果将平均时间复杂度降到了O(logn)，这是一个典型的用空间换时间数据结构。
跳表同样支持对数据进行高效的查找，插入和删除数据操作时间复杂度能与平衡二叉树媲美，最重要的是跳表的实现比平衡二叉树简单几个级别。
缺点就是“以空间换时间”方式存在一定数据冗余
跳表的实现原理
添加、删除操作都需要先查询出操作数据的位置，所以理解了跳表的查询原理后，剩下的只是对链表的操作。
链表不能像数组那样通过索引快速访问数据，只能沿着指针方向依次访问，所以不能使用二分查找算法快速进行数据查询。
数据链表：8 --> 13 --> 18 --> 23 --> 28 --> 33 --> 38
在原始链表的基础上，我们增加一层索引链表，假如原始链表的每两个结点就有一个结点也在索引链表当中，由于索引链表的结点个数是原始链表的一半，查找结点所需的访问次数也就相应减少了一半，经过两次查询我们便找到
索引链表：8 ----------> 18 ---------> 28 ---------> 38
数据链表：8 --> 13 --> 18 --> 23 --> 28 --> 33 --> 38
基于原始链表的第1层索引，抽出了第2层更为稀疏的索引，结点数量是第1层索引的一半。这样的多层索引可以进一步提升查询效率，
二层索引链表：8 ------------------------> 28
一层索引链表：8 ----------> 18 ---------> 28 ---------> 38
原始数据链表：8 --> 13 --> 18 --> 23 --> 28 --> 33 --> 38
Map
ConcurrentHashMap
基本原理
ConcurrentHashMap
- Java 7及之前版本（分段锁实现）：ConcurrentHashMap在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段；而每个Segment元素，它通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全
- 默认并发度 = 16：通过构造函数可配置（必须是2的幂次）
- 分段锁机制：将哈希表分成多个Segment（默认为16段），每个段独立加锁
- 并发写操作：不同段上的写操作可并行执行
- Java 8+版本（优化实现）：数组+链表+红黑树的方式实现，加锁则采用CAS和synchronized实现
- 并发度 ≈ 哈希桶数量：锁粒度细化到单个链表/红黑树节点（桶级别）
- CAS无锁化操作：使用sun.misc.Unsafe实现无锁化的tab数组访问和扩容操作
- 实际并发度：理论上等于哈希表桶的数量，但实际受硬件线程数限制
二义性（key value不能为null）
ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性
- null 是一个特殊的值，表示没有对象或没有引用。如果你用 null 作为键，那么你就无法区分这个键是否存在于 ConcurrentHashMap 中，还是根本没有这个键。
- 如果你用 null 作为值，那么你就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的，还是因为找不到对应的键而返回的。
拿 get 方法取值来说，返回的结果为 null 存在两种情况：
- 值没有在集合中 ；
- 值本身就是 null。
多线程环境下，存在一个线程操作该 ConcurrentHashMap 时，其他的线程将该 ConcurrentHashMap 修改的情况，所以无法通过 containsKey(key) 来判断否存在这个键值对
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个
复合操作的原子性保障
复合操作是指由多个基本操作(如put、get、remove、containsKey等)组成的操作
如先判断某个键是否存在containsKey(key)，然后根据结果进行插入或更新put(key, value)
示例如下
// 线程 A
if (!map.containsKey(key)) {
map.put(key, value);
}
// 线程 B
if (!map.containsKey(key)) {
map.put(key, anotherValue);
}
执行顺序如下：最终的结果是 (key, value)，而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题
- 线程 A 判断 map 中不存在 key线程
- B 判断 map 中不存在 key
- 线程 B 将 (key, anotherValue) 插入 map
- 线程 A 将 (key, value) 插入 map
ConcurrentHashMap 提供了一些原子性的复合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge等。
这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中
如此，上述的操作便可以改写为
// 线程 A
map.putIfAbsent(key, value);
// 线程 B
map.putIfAbsent(key, anotherValue);// 或者
// 线程 A
map.computeIfAbsent(key, k -> value);
// 线程 B
map.computeIfAbsent(key, k -> anotherValue);
也可以使用锁，但是不建议使用加锁的同步机制，违背了使用 ConcurrentHashMap 的初衷。在使用 ConcurrentHashMap 的时候，尽量使用这些原子性的复合操作方法来保证原子性
ConcurrentSkipListMap
ConcurrentSkipListMap 采用跳表（Skip List）数据结构，结合分层索引实现高效并发访问：
跳表节点结构
- 数据节点 (Node)：存储键值对，形成基础链表
- 索引节点 (Index)：建立多层索引，加快查找速度
区别
CopyOnWriteArraySet：基于CopyOnWriteArrayList实现，适用于读多写少的场景，写操作通过复制整个数组来实现线程安全，保证强一致性，但写性能差。
ConcurrentSkipListSet：基于跳表（Skip List）实现的有序集合，支持自然排序或自定义Comparator，并发访问性能较好，适合需要排序且高并发的场景。
ConcurrentHashMap：基于哈希表的并发映射，采用分段锁（JDK7）或CAS+synchronized（JDK8+），高并发下性能优异，适用于高频率的读写操作。
ConcurrentSkipListMap：同样基于跳表实现的有序映射，提供类似ConcurrentSkipListSet的特性，但用于键值对存储
并发容器对比
root((并发容器对比))数据结构CopyOnWriteArraySet: 动态数组ConcurrentSkipListSet: 跳表ConcurrentHashMap: 哈希表+链表/红黑树ConcurrentSkipListMap: 跳表线程安全机制COW类: 写时复制+ReentrantLockSkipList类: CAS+无锁算法CHM: CAS+synchronized(JDK8+)有序性有序: SkipList系列无序: COW/CHM时间复杂度写操作: COW(O(n)) > SkipList(O(log n)) > CHM(O(1))读操作: COW(O(1)) ≈ CHM(O(1)) > SkipList(O(log n))
Hashtable
Hashtable慢
- 全表锁机制
每个方法都使用synchronized修饰，锁住整个表对象
并发操作时形成串行化访问（同一时间仅一个线程能操作） - 性能瓶颈
读写操作都会触发全局锁
即使不同线程操作不同键值对，也无法并行处理
Hashtable的并发度 = 1，所有操作共享同一个锁，无论数据如何分布，每次只能有一个线程进行操作。
另外，Hashtable 基本被淘汰，不要在代码中使用它；
)
