讲义整理-并发容器

Myth丶恋晨 2023-01-14 05:56 130阅读 0赞

### 讲义整理-并发容器 ###

*  并发容器
 *   *  预备知识
     *   *  hash
         *  位运算
         *   *  二进制
             *  常用位运算
             *  位运算运用场景
     *  为什么要使用 ConcurrentHashMap
     *   *  1.7 中 HashMap 死循环分析
         *   *  HashMap 扩容流
             *  并发下的扩容
             *  总结
         *  ConcurrentHashMap
         *  ConcurrentHashMap 实现分析
         *   *  在 1.7 下的实现
             *  ConcurrentHashMap 的弱一致性
             *  size、containsValue
             *  在 1.8 下的实现
             *  与 1.8 中 HashMap 不同点：
     *  HashTable
     *   *  并发下的 Map 常见面试题汇总
         *   *  Q：HashMap 和 HashTable 有什么区别？
             *  Q：Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？
             *  HashMap & ConcurrentHashMap 的区别？
             *  Q：为什么 ConcurrentHashMap 比 HashTable 效率要高？
             *  Q：针对 ConcurrentHashMap 锁机制具体分析（JDK 1.7 VS JDK 1.8）？
             *  Q：ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized来代替重入锁 ReentrantLock？
             *  Q：ConcurrentHashMap 简单介绍
             *  Q：ConcurrentHashMap 的并发度是什么？
     *  ConcurrentSkipList 系列
     *   *  了解什么是 SkipList？
         *   *  二分查找和 AVL 树查找
             *  什么是跳表
     *  ConcurrentLinkedQueue
     *  写时复制容器
     *   *  什么是写时复制容器
         *  写时复制容器的问题
         *   *  性能问题
             *  数据一致性问题
     *  阻塞队列 BlockingQueu
     *   *  什么是阻塞队列
         *  常用阻塞队列
         *  有界无界？
         *  ArrayBlockingQueue
         *  LinkedBlockingQueue
         *  Array 实现和 Linked 实现的
         *  PriorityBlockingQueue
         *  DelayQueue
         *  SynchronousQueue
         *  LinkedTransferQueue
         *  LinkedBlockingDeque
         *  了解阻塞队列的实现原理

--------------------

# 并发容器 #

## 预备知识 ##

### hash ###

就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。常用 HASH 函数：直接取余法、乘法取整法、平方取中法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70]  
**处理冲突方法:**

1.  开放寻址法；
2.  再散列法：
3.  链地址法(拉链法)  
    常用 hash 算法的介绍：（1)MD4（2)MD5 它对输入仍以 512 位分组，其输出是4个32位字的级联（3)SHA-1 及其他。

### 位运算 ###

#### 二进制 ####

从小学一年级开始，我们就开始学加减乘除，特别是学加法的时候，刚开始算超过十的时候，如果不熟练，我们会掰着手指头数，有时候恨不得把脚趾头也加上。正是因为我们一般人有十个手指头，所以，从我们老老。。。祖先开始就用十进制。那计算机怎么办？计算机又没十个手指头。自然界要找出有十种状态的东西很难，但是只有两种状态的东西或者现象还是很容易的，所以计算机中要用二进制。

逢十进一，意味着至少两点，

1.  每个位上的数字不能超过 10，最大只能到9，
2.  如果某个位上的数字因为运算超过了 10，

**怎么办？**  
往高位进位。那么二进制也是一样的，不能说你二进制比较二，规则就不一样了，基本法还是要遵守的。  
**所以二进制里同样要遵循：**

1.  每个位上的数字不能超过 2，最大只能到 1，
2.  如果某个位上的数字因为运算超过了 2，

**怎么办？**

往高位进位  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 1]

#### 常用位运算 ####

*  位与 & (1&1=1 0&0=0 1&0=0)
 *  位或 | (1|1=1 0|0=0 1|0=1)
 *  位非 (1=0 ~0=1)
 *  位异或 ^ (1^1=0 1^0=1 0^0=0)
 *  有符号右移>>(若正数,高位补 0,负数,高位补 1)
 *  有符号左移<<
 *  无符号右移>>>(不论正负,高位均补 0

有趣的取模性质：取模 a % (2^n) 等价于 a & (2^n - 1)，所以在 map 里的数组个数一定是 2 的乘方数，计算 key 值在哪个元素中的时候，就用位运算来快速定位。

具体位运算的运行结果参见代码 cn.enjoyedu.ch5.bitwise. IntToBinary

#### 位运算运用场景 ####

Java 中的类修饰符、成员变量修饰符、方法修饰符，比如 Class 类中  
Java 容器中的 HashMap 和 ConcurrentHashMap 的实现  
权限控制或者商品属性  
简单可逆加密，比如异或运算(1^1=0 ;

*实战：权限控制*  
参见代码 cn.enjoyedu.ch5.bitwise. Permission

使用位运算的优劣势：  
节省很多代码量、效率高、属性变动影响小、不直观

## 为什么要使用 ConcurrentHashMap ##

### 1.7 中 HashMap 死循环分析 ###

在多线程环境下，使用 HashMap 进行 put 操作会引起死循环，导致 CPU 利用率接近 100%，HashMap 在并发执行 put 操作时会引起死循环，是因为多线程会导致 HashMap 的 Entry 链表  
形成环形数据结构，一旦形成环形数据结构，Entry 的 next 节点永远不为空，就会产生死循环获取 Entry。那么这个死循环是如何生成的呢？我们来仔细分析下。

#### HashMap 扩容流 ####

**原理**  
引发死循环，是在 HashMap 的扩容操作中。  
正常的扩容操作是这个流程。HashMap 的扩容在 put 操作中会触发扩容，主要是三个方法：  
![在这里插入图片描述][20210416163702313.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 3]  
综合来说，HashMap 一次扩容的过程：

1.  取当前 table 的 2 倍作为新 table 的大小
2.  根据算出的新 table 的大小 new 出一个新的 Entry 数组来，名为 newTable
3.  轮询原 table 的每一个位置，将每个位置上连接的 Entry，算出在新 table上的位置，并以链表形式连接
4.  原 table 上的所有 Entry 全部轮询完毕之后，意味着原 table 上面的所有Entry 已经移到了新的 table 上，HashMap 中的 table 指向 newTable

实例  
现在 hashmap 中有三个元素，Hash 表的 size=2, 所以 key = 3, 7, 5，在 mod 2以后都冲突在 table\[1\]这里了。  
![在这里插入图片描述][20210416163852184.png]  
按照方法中的代码![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 4]  
对 table\[1\]中的链表来说，进入 while 循环，此时 e=key(3)，那么 next=key(7)，经过计算重新定位 e=key(3)在新表中的位置，并把 e=key(3)挂在 newTable\[3\]的位置

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 6]  
这样循环下去，将 table\[1\]中的链表循环完成后，于是 HashMap 就完成了扩容

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 8]

#### 并发下的扩容 ####

上面都是单线程下的扩容，当多线程进行扩容时，会是什么样子呢？  
初始的 HashM 还是：  
![在这里插入图片描述][20210416164120383.png]  
我们现在假设有两个线程并发操作，都进入了扩容操作，![在这里插入图片描述][20210416164139687.png]我们以颜色进行区分两个线程。  
回顾我们的扩容代码，我们假设，线程 1 执行到 Entry<K,V> next = e.next;时被操作系统调度挂起了，而线程 2 执行完成了扩容操作  
![在这里插入图片描述][20210416164215284.png]  
于是，在线程 1,2 看来，就应该是这个样子![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 9]  
接下来，线程 1 被调度回来执行：  
1)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 10]  
2)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 11]  
3)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 12]  
4)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 13]  
5)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 14]  
6)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 15]  
7)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 16]  
循环列表产生后，一旦线程 1 调用 get（11,15 之类的元素）时，就会进入一个死循环的情况，将 CPU 的消耗到 100

#### 总结 ####

HashMap 之所以在并发下的扩容造成死循环，是因为，多个线程并发进行时，因为一个线程先期完成了扩容，将原 Map 的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。于是形成了一个环形链表，当 get 表中不存在的元素时，造成死循环。

### ConcurrentHashMap ###

*使用*  
除了 Map 系列应该有的线程安全的 get，put 等方法外，ConcurrentHashMap还提供了一个在并发下比较有用的方法 putIfAbsent，如果传入 key 对应的 value已经存在，就返回存在的 value，不进行替换。如果不存在，就添加 key 和 value，返回 null。在代码层面它的作用类似于：

synchronized(map){
    	if (map.get(key) == null){
    		return map.put(key, value);
    	} else{
    		return map.get(key);
    	}
    }

它让上述代码的整个操作是线程安全的。

### ConcurrentHashMap 实现分析 ###

#### 在 1.7 下的实现 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 17]  
![在这里插入图片描述][20210416165412264.png]  
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构。一个Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得与它对应的 Segment 锁。

构造方法和初始化  
![在这里插入图片描述][20210416165537548.png]  
ConcurrentHashMap 初始化方法是通过 initialCapacity、loadFactor 和concurrencyLevel(参数 concurrencyLevel 是用户估计的并发级别，就是说你觉得最多有多少线程共同修改这个 map，根据这个来确定 Segment 数组的大小concurrencyLevel 默认是 DEFAULT\_CONCURRENCY\_LEVEL = 16;)等几个参数来初始化 segment 数组、段偏移量 segmentShift、段掩码 segmentMask 和每个 segment里的 HashEntry 数组来实现的。

并发级别可以理解为程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数，实际上就是 ConcurrentHashMap 中的分段锁个数，即Segment\[\]的数组长度。ConcurrentHashMap 默认的并发度为 16，但用户也可以在构造函数中设置并发度。当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并发度（假如用户设置并发度为 17，实际并发度则为 32）。

如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个 Segment 内的访问会扩散到不同的 Segment 中，CPU cache 命中率会下降，从而引起程序性能下降。（文档的说法是根据你并发的线程数量决定，太多会导性能降低）

segments 数组的长度 ssize 是通过 concurrencyLevel 计算得出的。为了能通过按位与的散列算法来定位 segments 数组的索引，必须保证 segments 数组的长度是 2 的 N 次方（power-of-two size），所以必须计算出一个大于或等于concurrencyLevel 的最小的 2 的 N 次方值来作为 segments 数组的长度。假如concurrencyLevel 等于 14、15 或 16，ssize 都会等于 16，即容器里锁的个数也是16。

以下知识了解即可，无需深究

*初始化 segmentShift 和 segmentMask  
这两个全局变量需要在定位 segment 时的散列算法里使用，sshift 等于 ssize从 1 向左移位的次数，在默认情况下 concurrencyLevel 等于 16，1 需要向左移位移动 4 次，所以 sshift 等于 4。segmentShift 用于定位参与散列运算的位数，segmentShift 等于 32 减 sshift，所以等于 28，这里之所以用 32 是因为ConcurrentHashMap 里的 hash()方法输出的最大数是 32 位的。segmentMask 是散列运算的掩码，等于 ssize 减 1，即 15，掩码的二进制各个位的值都是 1。因为ssize 的最大长度是 65536，所以 segmentShift 最大值是 16，segmentMask 最大值是 65535，对应的二进制是 16 位，每个位都是 1。*

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 18]  
输入参数 initialCapacity 是 ConcurrentHashMap 的初始化容量，loadfactor 是每个 segment 的负载因子，在构造方法里需要通过这两个参数来初始化数组中的每个 segment。上面代码中的变量 cap 就是 segment 里 HashEntry 数组的长度，它等于 initialCapacity 除以 ssize 的倍数 c，如果 c 大于 1，就会取大于等于 c 的 2的 N 次方值，所以 segment 里 HashEntry 数组的长度不是 1，就是 2 的 N 次方。

在默认情况下， ssize = 16，initialCapacity = 16，loadFactor = 0.75f，那么 cap= 1，threshold = (int) cap \* loadFactor = 0。

既然 ConcurrentHashMap 使用分段锁 Segment 来保护不同段的数据，那么在插入和获取元素的时候，必须先通过散列算法定位到 Segment。ConcurrentHashMap 会首先使用 Wang/Jenkins hash 的变种算法对元素的hashCode 进行一次再散列。

ConcurrentHashMap 完全允许多个读操作并发进行，读操作并不需要加锁。ConcurrentHashMap 实现技术是保证 HashEntry 几乎是不可变的以及 volatile 关键字。  
![在这里插入图片描述][20210416165853112.png]  
get 操作  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 19]  
get 操作先经过一次再散列，然后使用这个散列值通过散列运算定位到Segment(使用了散列值的高位部分)，再通过散列算法定位到 table(使用了散列值的全部)。整个 get 过程，没有加锁，而是通过 volatile 保证 get 总是可以拿到最新值。

![在这里插入图片描述][20210416170018790.png]  
put 操作  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 20]  
ConcurrentHashMap 初始化的时候会初始化第一个槽 segment\[0\]，对于其他槽，在插入第一个值的时候再进行初始化。

ensureSegment 方法考虑了并发情况，多个线程同时进入初始化同一个槽segment\[k\]，但只要有一个成功就可以了。

具体实现是  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 21]  
![在这里插入图片描述][20210416170237158.png]  
put 方法会通过 tryLock()方法尝试获得锁，获得了锁，node 为 null 进入 try语句块，没有获得锁，调用 scanAndLockForPut 方法自旋等待获得锁。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 22]  
scanAndLockForPut 方法里在尝试获得锁的过程中会对对应 hashcode 的链表进行遍历，如果遍历完毕仍然找不到与 key 相同的 HashEntry 节点，则为后续的put 操作提前创建一个 HashEntry。当 tryLock 一定次数后仍无法获得锁，则通过lock 申请锁。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 23]  
在获得锁之后，Segment 对链表进行遍历，如果某个 HashEntry 节点具有相同的 key，则更新该 HashEntry 的 value 值，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 24]  
否则新建一个 HashEntry 节点，采用头插法，将它设置为链表的新 head 节点并将原头节点设为新 head 的下一个节点。新建过程中如果节点总数（含新建的 HashEntry）超过 threshold，则调用 rehash()方法对 Segment 进行扩容，最后将新建 HashEntry 写入到数组中。

rehash 操作  
扩容是新创建了数组，然后进行迁移数据，最后再将 newTable 设置给属性table。

为了避免让所有的节点都进行复制操作：由于扩容是基于 2 的幂指来操作，假设扩容前某 HashEntry 对应到 Segment 中数组的 index 为 i，数组的容量为capacity，那么扩容后该 HashEntry 对应到新数组中的 index 只可能为 i 或者i+capacity，因此很多 HashEntry 节点在扩容前后 index 可以保持不变。

假设原来 table 长度为 4，那么元素在 table 中的分布是这样的  
![在这里插入图片描述][20210416170801743.png]  
扩容后 table 长度变为 8，那么元素在 table 中的分布变成：  
![在这里插入图片描述][20210416170822143.png]  
可以看见 hash 值为 34 和 56 的下标保持不变，而 15,23,77 的下标都是在原来下标的基础上+4 即可，可以快速定位和减少重排次数。  
该方法没有考虑并发，因为执行该方法之前已经获取了锁。

remove 操作  
与 put 方法类似，都是在操作前需要拿到锁，以保证操作的线程安全性。

#### ConcurrentHashMap 的弱一致性 ####

然后对链表遍历判断是否存在 key 相同的节点以及获得该节点的 value。但由于遍历过程中其他线程可能对链表结构做了调整，因此 get 和 containsKey 返回的可能是过时的数据，这一点是 ConcurrentHashMap 在弱一致性上的体现。如果要求强一致性，那么必须使用 Collections.synchronizedMap()方法。

#### size、containsValue ####

这些方法都是基于整个 ConcurrentHashMap 来进行操作的，他们的原理也基本类似：首先不加锁循环执行以下操作：循环所有的 Segment，获得对应的值以及所有 Segment 的 modcount 之和。在 put、remove 和 clean 方法里操作元素前都会将变量 modCount 进行变动，如果连续两次所有 Segment 的 modcount和相等，则过程中没有发生其他线程修改 ConcurrentHashMap 的情况，返回获得的值。

当循环次数超过预定义的值时，这时需要对所有的 Segment 依次进行加锁，获取返回值后再依次解锁。所以一般来说，应该避免在多线程环境下使用 size和 containsValue 方法。

#### 在 1.8 下的实现 ####

改进

*  改进一：取消 segments 字段，直接采用 transient volatile HashEntry<K,V>\[\]table 保存数据，采用 table 数组元素作为锁，从而实现了对缩小锁的粒度，进一步减少并发冲突的概率，并大量使用了采用了 CAS + synchronized 来保证并发安全性。
 *  改进二：将原先 table 数组＋单向链表的数据结构，变更为 table 数组＋单向链表＋红黑树的结构。对于 hash 表来说，最核心的能力在于将 key hash 之后能均匀的分布在数组中。如果 hash 之后散列的很均匀，那么 table 数组中的每个队列长度主要为 0 或者 1。但实际情况并非总是如此理想，虽然ConcurrentHashMap 类默认的加载因子为 0.75，但是在数据量过大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，如果还是采用单向列表方式，那么查询某个节点的时间复杂度为 O(n)；因此，对于个数超过 8(默认值)的列表，  
    jdk1.8 中采用了红黑树的结构，那么查询的时间复杂度可以降低到 O(logN)，可以改进性能。

使用 Node（1.7 为 Entry） 作为链表的数据结点，仍然包含 key，value，hash 和 next 四个属性。 红黑树的情况使用的是 TreeNode（extends Node）。

根据数组元素中，第一个结点数据类型是 Node 还是 TreeNode 可以判断该位置下是链表还是红黑树。  
用于判断是否需要将链表转换为红黑树的阈值  
![在这里插入图片描述][20210416171239110.png]  
用于判断是否需要将红黑树转换为链表的阈值  
![在这里插入图片描述][20210416171303262.png]  
核心数据结构和属性  
**Node**  
Node 是最核心的内部类，它包装了 key-value 键值对。  
![在这里插入图片描述][20210416171415153.png]  
定义基本和 1.7 中的 HashEntry 相同。而这个 map 本身所持有的也是一个Node 型的数组  
![在这里插入图片描述][20210416171440363.png]  
增加了一个 find 方法来用以辅助 map.get()方法。其实就是遍历链表，子类中会覆盖这个方法。  
![在这里插入图片描述][20210416171511651.png]  
在 map 中还定义了 Segment 这个类，不过只是为了向前兼容而已，不做过多考虑。

**TreeNode**  
树节点类，另外一个核心的数据结构。当链表长度过长的时候，会转换为TreeNode。  
![在这里插入图片描述][20210416171557752.png]

#### 与 1.8 中 HashMap 不同点： ####

1.  它并不是直接转换为红黑树，而是把这些结点放在 TreeBin 对象中，由TreeBin 完成对红黑树的包装。
2.  TreeNode 在 ConcurrentHashMap 扩展自 Node 类，而并非 HashMap 中的扩展自 LinkedHashMap.Entry<K,V>类，也就是说 TreeNode 带有 next 指

**TreeBin**  
负责 TreeNode 节点。它代替了 TreeNode 的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是 TreeBin 对象，而不是 TreeNode 对象。  
另外这个类还带有了读写锁机制。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 25]  
**特殊的 ForwardingNode**  
一个特殊的 Node 结点，hash 值为 -1，其中存储 nextTable 的引用。有table 发生扩容的时候，ForwardingNode 发挥作用，作为一个占位符放在 table中表示当前结点为 null 或者已经被移动。

**sizeCtl**  
用来控制 table 的初始化和扩容操作。  
负数代表正在进行初始化或扩容操作

*  \-1 代表正在初始化
 *  \-N 表示有 N-1 个线程正在进行扩容操作  
    0 为默认值，代表当时的 table 还没有被初始化  
    正数表示初始化大小或 Map 中的元素达到这个数量时，需要进行扩容了。

**核心方法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 26]  
**构造方法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 27]  
可以发现，在 new 出一个 map 的实例时，并不会创建其中的数组等等相关的部件，只是进行简单的属性设置而已，同样的，table 的大小也被规定为必须是 2 的乘方数。

真正的初始化在放在了是在向 ConcurrentHashMap 中插入元素的时候发生的。如调用 put、computeIfAbsent、compute、merge 等方法的时候，调用时机是检查 table==null。

**get 操作**  
get 方法比较简单，给定一个 key 来确定 value 的时候，必须满足两个条件key 相同 hash 值相同，对于节点可能在链表或树上的情况，需要分别去查找。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 28]  
**put 操作**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 29]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 30]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 31]  
**总结来说**，put 方法就是，沿用 HashMap 的 put 方法的思想，根据 hash 值计算这个新插入的点在 table 中的位置 i，如果 i 位置是空的，直接放进去，否则进行判断，如果 i 位置是树节点，按照树的方式插入新的节点，否则把 i 插入到链表的末尾。

整体流程上，就是首先定义不允许 key 或 value 为 null 的情况放入 对于每一个放入的值，首先利用 spread 方法对 key 的 hashcode 进行一次 hash 计算，由此来确定这个值在 table 中的位置。

如果这个位置是空的，那么直接放入，而且不需要加锁操作。

如果这个位置存在结点，说明发生了 hash 碰撞，首先判断这个节点的类型。如果是链表节点,则得到的结点就是 hash 值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到 hash 值与 key 值都与新加入节点是一致的情况，则只需要更新 value 值即可。否则依次向后遍历，直到链表尾插入这个结点。如果加入这个节点以后链表长度大于 8，就把这个链表转换成红黑树。如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。

**初始化**  
前面说过，构造方法中并没有真正初始化，真正的初始化在放在了是在向ConcurrentHashMap 中插入元素的时候发生的。具体实现的方法就是 initTable  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 32]  
**transfer**  
当 ConcurrentHashMap 容量不足的时候，需要对 table 进行扩容。这个方法的基本思想跟 HashMap 是很像的，但是由于它是支持并发扩容的，所以要复杂的多。我们不深入源码去讲述，只讲述其大概原理。

为何要并发扩容？因为在扩容的时候，总是会涉及到从一个“数组”到另一个“数组”拷贝的操作，如果这个操作能够并发进行，就能利用并发处理去减少扩容带来的时间影响。

整个扩容操作分为两个部分：  
第一部分是构建一个 nextTable,它的容量是原来的 2 倍。  
![在这里插入图片描述][20210416233947974.png]  
第二个部分就是将原来 table 中的元素复制到 nextTable 中，这里允许多线程进行操作。

整个扩容流程就是遍历和复制：

为 null 或者已经处理过的节点，会被设置为 forwardNode 节点，当线程准备扩容时，发现节点是 forwardNode 节点，跳过这个节点，继续寻找未处理的节点，找到了，对节点上锁，  
如果这个位置是 Node 节点（fh>=0），说明它是一个链表，就构造一个反序链表，把他们分别放在 nextTable 的 i 和 i+n 的位置上

如果这个位置是 TreeBin 节点（fh<0），也做一个反序处理，并且判断是否需要红黑树转链表，把处理的结果分别放在 nextTable 的 i 和 i+n 的位置上

遍历过所有的节点以后就完成了复制工作，这时让 nextTable 作为新的 table，并且更新 sizeCtl 为新容量的 0.75 倍 ，完成扩容。

并发扩容其实就是将数据迁移任务拆分成多个小迁移任务，在实现上使用了一个变量 stride 作为步长控制，每个线程每次负责迁移其中的一部分。

**remove**  
移除方法的基本流程和 put 方法很类似，只不过操作由插入数据变为移除数据而已，而且如果存在红黑树的情况下，会检查是否需要将红黑树转为链表的步骤。不再重复讲述。

**treeifyBin**

用于将过长的链表转换为 TreeBin 对象。但是他并不是直接转换，而是进行一次容量判断，如果容量没有达到转换的要求，直接进行扩容操作并返回；如果满足条件才将链表的结构转换为 TreeBin ，这与 HashMap 不同的是，它并没有把 TreeNode 直接放入红黑树，而是利用了 TreeBin 这个小容器来封装所有的TreeNode。

**size**  
在 JDK1.8 版本中，对于 size 的计算，在扩容和 addCount()方法就已经有处理了，可以注意一下 Put 函数，里面就有 addCount()函数，早就计算好的，然后你size 的时候直接给你。JDK1.7 是在调用 size()方法才去计算，其实在并发集合中去计算 size 是没有多大的意义的，因为 size 是实时在变的。

在具体实现上，计算大小的核心方法都是 sumCount()  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 33]  
可以看见，统计数量时使用了 baseCount、和 CounterCell 类型的变量counterCells 。其实 baseCount 就是记录容器数量的，而 counterCells 则是记录CAS 更新 baseCounter 值时，由于高并发而导致失败的值。这两个变量的变化在addCount() 方法中有体现，  
**大致的流程就是：**

1.  对 baseCount 做 CAS 自增操作。
2.  如果并发导致 baseCount CAS 失败了，则使用 counterCells。
3.  如果 counterCells CAS 失败了，在 fullAddCount 方法中，会继续死循环操作，直到成功。

## HashTable ##

HashTable 容器使用 synchronized 来保证线程安全，但在线程竞争激烈的情况下 HashTable 的效率非常低下。因为当一个线程访问 HashTable 的同步方法，其他线程也访问 HashTable 的同步方法时，会进入阻塞或轮询状态。如线程 1 使用 put 进行元素添加，线程 2 不但不能使用 put 方法添加元素，也不能使用 get方法来获取元素，所以竞争越激烈效率越低。

### 并发下的 Map 常见面试题汇总 ###

#### Q：HashMap 和 HashTable 有什么区别？ ####

1.  HashMap 是线程不安全的，HashTable 是线程安全的；
2.  由于线程安全，所以 HashTable 的效率比不上 HashMap；
3.  HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null，而 HashTable 不允许；
4.  HashMap 默认初始化数组的大小为 16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；
5.  HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的hashCode

#### Q：Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？ ####

ConcurrentHashMap 类（是 Java 并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）；  
而针对 ConcurrentHashMap，在 JDK 1.7 中采用分段锁的方式；JDK 1.8 中直接采用了 CAS（无锁算法）+ synchronized，也采用分段锁的方式并大大缩小了锁的粒度。

#### HashMap & ConcurrentHashMap 的区别？ ####

除了加锁，原理上无太大区别。  
另外，HashMap 的键值对允许有 null，但是 ConCurrentHashMap 都不允许。在数据结构上，红黑树相关的节点类

#### Q：为什么 ConcurrentHashMap 比 HashTable 效率要高？ ####

HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；  
ConcurrentHashMapJDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基  
于 Segment，包含多个 HashEntry。  
JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

#### Q：针对 ConcurrentHashMap 锁机制具体分析（JDK 1.7 VS JDK 1.8）？ ####

JDK 1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。

1.  Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个Segment 对象守护每个散列映射表的若干个桶；
2.  HashEntry 用来封装映射表的键-值对；
3.  每个桶是由若干个 HashEntry 对象链接起来的链表。

JDK 1.8 中，采用 Node + CAS + Synchronized 来保证并发安全。取消类Segment，直接用 table 数组存储键值对；当 HashEntry 对象组成的链表长度超过 TREEIFY\_THRESHOLD 时，链表转换为红黑树，提升性能。底层变更为数组 +链表 + 红黑树。

#### Q：ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized来代替重入锁 ReentrantLock？ ####

1.  JVM 开发团队在 1.8 中对 synchronized 做了大量性能上的优化，而且基于 JVM 的 synchronized 优化空间更大，更加自然。
2.  在大量的数据操作下，对于 JVM 的内存压力，基于 API 的ReentrantLock 会开销更多的内存。

#### Q：ConcurrentHashMap 简单介绍 ####

1.  重要的常量：  
    private transient volatile int sizeCtl;  
    当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容；  
    当为 0 时，表示 table 还没有初始化；  
    当为其他正数时，表示初始化或者下一次进行扩容的大小。
2.  数据结构：  
    Node 是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据；  
    TreeNode 继承 Node，但是数据结构换成了二叉树结构，是红黑树的存储  
    结构，用于红黑树中存储数据；  
    TreeBin 是封装 TreeNode 的容器，提供转换红黑树的一些条件和锁的控制。
3.  存储对象时（put() 方法）：
    
     *  如果没有初始化，就调用 initTable() 方法来进行初始化；
     *  如果没有 hash 冲突就直接 CAS 无锁插入；
     *  如果需要扩容，就先进行扩容；
     *  如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入；
     *  如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一次进入循环
     *  如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容。
4.  扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍。  
    helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高。
5.  获取对象时（get()方法）：
    
     *  计算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；
     *  如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法，查找该结点，匹配就返回；
     *  以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null。

#### Q：ConcurrentHashMap 的并发度是什么？ ####

1.7 中程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并发度（假如用户设置并发度为 17，实际并发度则为 32）。  
1.8 中并发度则无太大的实际意义了，主要用处就是当设置的初始容量小于并发度，将初始容量提升至并发度大小。

## ConcurrentSkipList 系列 ##

ConcurrentSkipListMap 有序 Map  
ConcurrentSkipListSet

TreeMap 和 TreeSet 使用红黑树按照 key 的顺序（自然顺序、自定义顺序）来使得键值对有序存储，但是只能在单线程下安全使用；多线程下想要使键值对按照 key 的顺序来存储，则需要使用 ConcurrentSkipListMap 和ConcurrentSkipListSet，分别用以代替 TreeMap 和 TreeSet，存入的数据按 key 排序。在实现上，ConcurrentSkipListSet 本质上就是 ConcurrentSkipListMap。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 34]

### 了解什么是 SkipList？ ###

#### 二分查找和 AVL 树查找 ####

二分查找要求元素可以随机访问，所以决定了需要把元素存储在连续内存。这样查找确实很快，但是插入和删除元素的时候，为了保证元素的有序性，就需要大量的移动元素了。

如果需要的是一个能够进行二分查找，又能快速添加和删除元素的数据结构，首先就是二叉查找树，二叉查找树在最坏情况下可能变成一个链表。

于是，就出现了平衡二叉树，根据平衡算法的不同有 AVL 树，B-Tree，B+Tree，红黑树等，但是 AVL 树实现起来比较复杂，平衡操作较难理解，这时候就可以用SkipList 跳跃表结构。

#### 什么是跳表 ####

传统意义的单链表是一个线性结构，向有序的链表中插入一个节点需要 O(n)的时间，查找操作需要 O(n)的时间。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 35]  
如果我们使用上图所示的跳跃表，就可以减少查找所需时间为 O(n/2)，因为我们可以先通过每个节点的最上面的指针先进行查找，这样子就能跳过一半的节点。

比如我们想查找 50，首先和 20 比较，大于 20 之后，在和 40 进行比较，然后在和 70 进行比较，发现 70 大于 50，说明查找的点在 40 和 50 之间，从这个过程中，我们可以看出，查找的时候跳过了 30。

跳跃表其实也是一种通过“空间来换取时间”的一个算法，令链表的每个结点不仅记录 next 结点位置，还可以按照 level 层级分别记录后继第 level 个结点。此法使用的就是“**先大步查找确定范围，再逐渐缩小迫近**”的思想进行的查找。跳跃表在算法效率上很接近红黑树。

跳跃表又被称为概率，或者说是随机化的数据结构，目前开源软件 Redis 和lucence 都有用到它。

都是线程安全的 Map 实现，ConcurrentHashMap 的性能和存储空间要优于ConcurrentSkipListMap，但是 ConcurrentSkipListMap 有一个功能： 它会按照键的顺序进行排序。

## ConcurrentLinkedQueue ##

无界非阻塞队列，它是一个基于链表的无界线程安全队列。该队列的元素遵循先进先出的原则。头是最先加入的，尾是最近加入的。插入元素是追加到尾上。提取一个元素是从头提取。

大家可以看成是 LinkedList 的并发版本，常用方法：  
concurrentLinkedQueue.add(“c”);  
concurrentLinkedQueue.offer(“d”); // 将指定元素插入到此队列的尾部。  
concurrentLinkedQueue.peek(); // 检索并不移除此队列的头，如果此队列为空，则返回 null。

concurrentLinkedQueue.poll(); // 检索并移除此队列的头，如果此队列为空，则返回 null。

## 写时复制容器 ##

### 什么是写时复制容器 ###

CopyOnWriteArrayList 和 CopyOnWriteArraySet  
CopyOnWrite 容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

这样做的好处是我们可以对 CopyOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，读和写不同的容器。如果读的时候有多个线程正在向 CopyOnWriteArrayList添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的CopyOnWriteArrayList。

CopyOnWrite 并发容器用于对于绝大部分访问都是读，且只是偶尔写的并发场景。比如白名单，黑名单，商品类目的访问和更新场景，假如我们有一个搜索网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中，黑名单每天晚上更新一次。当用户搜索时，会检查当前关键字在不在黑名单当中，如果在，则提示不能搜索。

使用 CopyOnWriteMap 需要注意两件事情：

1.  减少扩容开销。根据实际需要，初始化 CopyOnWriteMap 的大小，避免写时 CopyOnWriteMap 扩容的开销。
2.  使用批量添加。因为每次添加，容器每次都会进行复制，所以减少添加次数，可以减少容器的复制次数。

### 写时复制容器的问题 ###

#### 性能问题 ####

每次修改都创建一个新数组，然后复制所有内容，如果数组比较大，修改操作又比较频繁，可以想象，性能是很低的，而且内存开销会很大。

#### 数据一致性问题 ####

CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，不要使用 CopyOnWrite 容器。

## 阻塞队列 BlockingQueu ##

队列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 36]  
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

### 什么是阻塞队列 ###

1.  支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满。
2.  支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空。

在并发编程中使用**生产者和消费者模式**能够解决绝大多数并发问题。该模式通过平衡生产线程和消费线程的工作能力来提高程序整体处理数据的速度。

在线程世界里，生产者就是生产数据的线程，消费者就是消费数据的线程。在多线程开发中，如果生产者处理速度很快，而消费者处理速度很慢，那么生产者就必须等待消费者处理完，才能继续生产数据。同样的道理，如果消费者的处理能力大于生产者，那么消费者就必须等待生产者。

为了解决这种生产消费能力不均衡的问题，便有了生产者和消费者模式。生产者和消费者模式是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通信，而是通过阻塞队列来进行通信，所以生产者生产完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据，而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。

阻塞队列常用于生产者和消费者的场景，生产者是向队列里添加元素的线程，消费者是从队列里取元素的线程。阻塞队列就是生产者用来存放元素、消费者用来获取元素的容器。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 37]

*  抛出异常：当队列满时，如果再往队列里插入元素，会抛出IllegalStateException（“Queuefull”）异常。当队列空时，从队列里获取元素会抛出 NoSuchElementException 异常。
 *  返回特殊值：当往队列插入元素时，会返回元素是否插入成功，成功返回true。如果是移除方法，则是从队列里取出一个元素，如果没有则返回 null。
 *  一直阻塞：当阻塞队列满时，如果生产者线程往队列里 put 元素，队列会一直阻塞生产者线程，直到队列可用或者响应中断退出。当队列空时，如果消费者线程从队列里 take 元素，队列会阻塞住消费者线程，直到队列不为空。
 *  超时退出：当阻塞队列满时，如果生产者线程往队列里插入元素，队列会阻塞生产者线程一段时间，如果超过了指定的时间，生产者线程就会退出。

### 常用阻塞队列 ###

*  ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。
 *  LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。
 *  PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。
 *  DelayQueue：一个使用优先级队列实现的无界阻塞队列。
 *  SynchronousQueue：一个不存储元素的阻塞队列。
 *  LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
 *  LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

以上的阻塞队列都实现了 BlockingQueue 接口，也都是线程安全的。

### 有界无界？ ###

有限队列就是长度有限，满了以后生产者会阻塞，无界队列就是里面能放无数的东西而不会因为队列长度限制被阻塞，当然空间限制来源于系统资源的限制，如果处理不及时，导致队列越来越大越来越大，超出一定的限制致使内存超限，操作系统或者 JVM 帮你解决烦恼，直接把你 OOM kill 省事了。

无界也会阻塞，为何？因为阻塞不仅仅体现在生产者放入元素时会阻塞，消费者拿取元素时，如果没有元素，同样也会阻塞。

### ArrayBlockingQueue ###

是一个用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不保证线程公平的访问队列，所谓公平访问队列是指阻塞的线程，可以按照阻塞的先后顺序访问队列，即先阻塞线程先访问队列。非公平性是对先等待的线程是非公平的，当队列可用时，阻塞的线程都可以争夺访问队列的资格，有可能先阻塞的线程最后才访问队列。初始化时有参数可以设置。

### LinkedBlockingQueue ###

是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为Integer.MAX\_VALUE。此队列按照先进先出的原则对元素进行排序。

### Array 实现和 Linked 实现的 ###

1.  队列中锁的实现不同  
    ArrayBlockingQueue 实现的队列中的锁是没有分离的，即生产和消费用的是同一个锁；  
    LinkedBlockingQueue 实现的队列中的锁是分离的，即生产用的是 putLock，消费是 takeLock
2.  在生产或消费时操作不同  
    ArrayBlockingQueue 实现的队列中在生产和消费的时候，是直接将枚举对象插入或移除的；  
    LinkedBlockingQueue 实现的队列中在生产和消费的时候，需要把枚举对象转换为 Node进行插入或移除，会影响性能
3.  队列大小初始化方式不同  
    ArrayBlockingQueue 实现的队列中必须指定队列的大小；  
    LinkedBlockingQueue 实现的队列中可以不指定队列的大小，但是默认是Integer.MAX\_VALUE

### PriorityBlockingQueue ###

PriorityBlockingQueue 是一个支持优先级的无界阻塞队列。默认情况下元素采取自然顺序升序排列。也可以自定义类实现 compareTo()方法来指定元素排序规则，或者初始化 PriorityBlockingQueue 时，指定构造参数 Comparator 来对元素进行排序。需要注意的是不能保证同优先级元素的顺序。

### DelayQueue ###

是一个支持延时获取元素的无界阻塞队列。队列使用 PriorityQueue 来实现。队列中的元素必须实现 Delayed 接口，在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。

DelayQueue 非常有用，可以将 DelayQueue 运用在以下应用场景。  
缓存系统的设计：可以用 DelayQueue 保存缓存元素的有效期，使用一个线程循环查询 DelayQueue，一旦能从 DelayQueue 中获取元素时，表示缓存有效期到了。  
还有订单到期，限时支付等等

### SynchronousQueue ###

是一个不存储元素的阻塞队列。每一个 put 操作必须等待一个 take 操作，否则不能继续添加元素。SynchronousQueue 可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。队列本身并不存储任何元素，非常适合传递性场景。SynchronousQueue 的吞吐量高于 LinkedBlockingQueue 和ArrayBlockingQueue。

### LinkedTransferQueue ###

多了 tryTransfer 和 transfer 方法。

1.  transfer 方法  
    如果当前有消费者正在等待接收元素（消费者使用 take()方法或带时间限制的 poll()方法时），transfer 方法可以把生产者传入的元素立刻 transfer（传输）给消费者。如果没有消费者在等待接收元素，transfer 方法会将元素存放在队列的 tail 节点，并等到该元素被消费者消费了才返回。
2.  tryTransfer 方法  
    tryTransfer 方法是用来试探生产者传入的元素是否能直接传给消费者。如果没有消费者等待接收元素，则返回 false。和 transfer 方法的区别是 tryTransfer 方法无论消费者是否接收，方法立即返回，而 transfer 方法是必须等到消费者消费了才返回。

### LinkedBlockingDeque ###

LinkedBlockingDeque 是一个由链表结构组成的双向阻塞队列。所谓双向队列指的是可以从队列的两端插入和移出元素。双向队列因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争。

多了 addFirst、addLast、offerFirst、offerLast、peekFirst 和 peekLast 等方法，以 First 单词结尾的方法，表示插入、获取（peek）或移除双端队列的第一个元素。以 Last 单词结尾的方法，表示插入、获取或移除双端队列的最后一个元素。另外，插入方法 add 等同于 addLast，移除方法 remove 等效于 removeFirst。但是 take 方法却等同于 takeFirst，不知道是不是 JDK 的 bug，使用时还是用带有 First和 Last 后缀的方法更清楚。在初始化 LinkedBlockingDeque 时可以设置容量防止其过度膨胀。另外，双向阻塞队列可以运用在“工作窃取”模式中。

### 了解阻塞队列的实现原理 ###

使用了等待通知模式实现。  
所谓**通知模式**：  
就是当生产者往满的队列里添加元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。通过查看 JDK 源码发现 ArrayBlockingQueue 使用了 Condition 来实现。其余队列的实现，大家可以自行查看，队列的实现的代码总体来说，并不复杂。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70]: /images/20221022/a40465f073a6421181f88a14318ddda7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/108f9aecfea345bbb7f4b969fa2de385.png
[20210416163702313.png]: https://img-blog.csdnimg.cn/20210416163702313.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/5c97f8f7286d44b394f4fa767a09eb5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 3]: /images/20221022/ad4637094a7f4f3faad6309b95df0804.png
[20210416163852184.png]: /images/20221022/d0c6b73d4f774ec499a8051cf7c5617f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 4]: /images/20221022/adf5709f58dd4b1e8907f83fed54d6fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 5]: /images/20221022/efaac9e493d4453ea498ae5562238d03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 6]: /images/20221022/3e5f840f284840b1a34799d50a6c12aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 7]: /images/20221022/8a08e2991c6140cba04887275bad0b12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 8]: /images/20221022/11fbe07ea7f34378ac99f508becf8154.png
[20210416164120383.png]: /images/20221022/c3c537fed31c48cc99604c58285c3866.png
[20210416164139687.png]: /images/20221022/f544607bd27340ec8ce0829e2f9cd957.png
[20210416164215284.png]: /images/20221022/9c055b7be4914b08af8bd772d0f1f446.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 9]: /images/20221022/08c0d9476fd942bd9cfcb481579cafc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 10]: /images/20221022/6c0dd9ed4c4c497b9962b96f825d99e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 11]: /images/20221022/340504f08b43472984a45c5b9b20bd1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 12]: /images/20221022/01cdac334cd54043a242ecc5b912fe38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 13]: /images/20221022/0fe7a48aaf3044d1a3f00861bfcf8e0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 14]: /images/20221022/ae2779b61a5e459096123bd57c109a5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 15]: /images/20221022/bc274af0070c4b6f8609b3bc62e337c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 16]: /images/20221022/de4338ecd8ba42a38e2b5e6d3ec179ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 17]: /images/20221022/6b62889f1c01485bbe6678563483f0da.png
[20210416165412264.png]: /images/20221022/b8f2d36cb8a941f799af27f955964974.png
[20210416165537548.png]: /images/20221022/c9536cfaf16d4612a518880922faece3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 18]: /images/20221022/1403df7fe8664e59977ec5bfe27ee872.png
[20210416165853112.png]: /images/20221022/11b6c0f37a154e3bb1e62950c6e0b9b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 19]: /images/20221022/83f98511f7724f8689de0f5efa38d4ef.png
[20210416170018790.png]: /images/20221022/f4b79a4d6ed544cc8532bd344be826d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 20]: /images/20221022/27c8ae70f13748938b29809cea090396.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 21]: /images/20221022/828a7f39452649d2a33734a13dcc0972.png
[20210416170237158.png]: /images/20221022/c7620c29fc5b4be68ccf8fd00f596c92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 22]: /images/20221022/8e4dfcac26fc4261b05af9c0c87eaab8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 23]: /images/20221022/2e7146317667496cace3ec08af5b9430.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 24]: /images/20221022/36c2f90abb934e4fa1f6ed17ebf89342.png
[20210416170801743.png]: /images/20221022/5dd92cfa0a164c00ac5adee6da96eb41.png
[20210416170822143.png]: /images/20221022/645ee7fd876c4f5a97a35d146105ce94.png
[20210416171239110.png]: /images/20221022/1ada81aa0fa04bd79df562038e50efc5.png
[20210416171303262.png]: /images/20221022/eca5f1bf49f34cce8ea28cc5a640dcd5.png
[20210416171415153.png]: /images/20221022/12a2be38f53247b79e085c7b1b7263e9.png
[20210416171440363.png]: /images/20221022/0a7f37fca4a44f189d91fe641678d715.png
[20210416171511651.png]: /images/20221022/8b5d33f35d674d2795ec18ab94eaff07.png
[20210416171557752.png]: /images/20221022/7b0b68bca7cf4094bb4ffd1d79540fff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 25]: /images/20221022/260f8b70a8104e84822457aa7c39665e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 26]: /images/20221022/7b9e7bbb709740b2ae546f4867c9db79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 27]: /images/20221022/7a0dde6b4a09466893dcec37fbc7fe5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 28]: /images/20221022/a29dc51aa09f49749de02aceb0dc23e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 29]: /images/20221022/a71158d9e33d480a9937865e001e2d53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 30]: /images/20221022/b9a3e08ffb194404b42f55a4f9804935.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 31]: /images/20221022/9498038390994fa9a43237c89704bb0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 32]: /images/20221022/be7c65b62b4744ad8702cf2c8c14d643.png
[20210416233947974.png]: /images/20221022/c01779dcbc8a46edac82f5e919b96bfe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 33]: /images/20221022/d7a18be172964f44bcf4729bf632343f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 34]: /images/20221022/44c3be13cb3d4612bf9f256301fa819a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 35]: /images/20221022/ead53fdb3371458980f99689104cffba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 36]: /images/20221022/e9aa55a1d6ca4821842a9c6c9181914e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlZW5zdHlsZQ_size_16_color_FFFFFF_t_70 37]: /images/20221022/3c5645d0ac704faf81c5c9924d52270e.png