java多线程之并发容器集合

一、多线程操作容器存在的问题

如下代码

public class NotSafeDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString());
                System.out.println(list);
            }, "线程" + i).start();
        }
    }
}

执行以上代码，当我们多个线程同时对集合进行修改，会发生java.util.ConcurrentModificationException异常，

Vector 是矢量队列，它是 JDK1.0 版本添加的类。继承于 AbstractList，实现 了 List, RandomAccess, Cloneable 这些接口。 Vector 继承了 AbstractList， 实现了 List；所以，它是一个队列，支持相关的添加、删除、修改、遍历等功 能。 Vector 实现了 RandmoAccess 接口，即提供了随机访问功能。 RandmoAccess 是 java 中用来被 List 实现，为 List 提供快速访问功能的。在 Vector 中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访 问。 Vector 实现了 Cloneable 接口，即实现 clone()函数。它能被克隆，和 ArrayList 不同，Vector 中的操作是线程安全的

对上面的代码稍作修改

public class NotSafeDemo {
    public static void main(String[] args) {
        List list = new Vector();
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString());
                System.out.println(list);
            }, "线程" + i).start();
        }
    }
}

执行并没有发现什么异常，查看vector源码的add方法，我们发现add 方法被 synchronized 同步修辞,线程安全!因此没有并发异常，同样Collections 提供了方法 synchronizedList 也保证 list 是同步线程安全的，如下代码执行也不会发生异常

public class NotSafeDemo {
    public static void main(String[] args) {
        List list = Collections.synchronizedList(new ArrayList<>());
        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString());
                System.out.println(list);
            }, "线程" + i).start();
        }
    }
}

HashTable和Vector一样都是线程安全的容器类，但是这些容器实现同步的⽅式是通过对⽅法加锁(sychronized)⽅式实现的， 这样读写均需要锁操作，导致性能低下，即使是Vector这样线程安全的类，在⾯对多线程下的复合操作的时候也是需要通过客户端加锁的⽅式保证原⼦性

案例：

public class TestVector {
 private Vector<String> vector;
 //⽅法⼀
 public Object getLast(Vector vector) {
 int lastIndex = vector.size() - 1;
 return vector.get(lastIndex);
 }
 //⽅法⼆
 public void deleteLast(Vector vector) {
 int lastIndex = vector.size() - 1;
 vector.remove(lastIndex);
 }
 //⽅法三
 public Object getLastSysnchronized(Vector vector) {
 synchronized(vector){
 int lastIndex = vector.size() - 1;
 return vector.get(lastIndex);
 }
 }
 //⽅法四
 public void deleteLastSysnchronized(Vector vector) {
 synchronized (vector){
 int lastIndex = vector.size() - 1;
 vector.remove(lastIndex);
 }
 }
}

如果⽅法⼀和⽅法⼆为⼀个组合的话。那么当⽅法⼀获取到了 vector 的size之 后，⽅法⼆已经执⾏完毕，这样就导致程序的错误。

如果⽅法三与⽅法四组合的话。通过锁机制保证了在 vector 上的操作的原⼦性。

并发容器是Java 5 提供的在多线程编程下⽤于代替同步容器，针对不同的应⽤场景 进⾏设计，提⾼容器的并发访问性，同时定义了线程安全的复合操作，针对queue、List、Map、Set、Deque等，java.util.concurrent包提供了对应的并发集合类

二、并发map

在并发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非 常低下，基于以上两个原因，便有了ConcurrentHashMap

（1）线程不安全的HashMap 在多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，所 以在并发情况下不能使用HashMap。例如，执行以下代码会引起死循环

    final HashMap<String, String> map = new HashMap<String, String>(2);
    Thread t = new Thread(new Runnable() {
        @Override
        public void run() {
            for (int i = 0; i < 10000; i++) {
                new Thread(new Runnable() {
                    @Override
                    public void run() {
                        map.put(UUID.randomUUID().toString(), "");
                    }
                }, "ftf" + i).start();
            }
        }
    }, "ftf");
t.start();
t.join();

HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表 形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获 取Entry。

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

（3）ConcurrentHashMap的锁分段技术可有效提升并发访问率 HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的 线程都必须竞争同一把锁，假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么 当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效提高并 发访问效率，这就是ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存 储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数 据也能被其他线程访问

ConcurrentMap接⼝继承了Map接⼝，在Map接⼝的基础上⼜定义了四个⽅法：

public interface ConcurrentMap<K, V> extends Map<K, V> {
 //插⼊元素，与原有put⽅法不同的是，putIfAbsent⽅法中如果插⼊的key相同，
则不替换原有的value值
 V putIfAbsent(K key, V value);
 //移除元素，与原有remove⽅法不同的是，新remove⽅法中增加了对value的判断，
如果要删除的key-value不能与Map中原有的key-value对应上，则不会删除该元素
 boolean remove(Object key, Object value);
 //替换元素，增加了对value值的判断，如果key-oldValue能与Map中原有的
key-value对应上，才进⾏替换操作
 boolean replace(K key, V oldValue, V newValue);
 //替换元素，与上⾯的replace不同的是，此replace不会对Map中原有的keyvalue进⾏⽐较，如果key存在则直接替换
 V replace(K key, V value);
}

ConcurrentHashMap同HashMap⼀样也是基于散列表的map，但是它提供了⼀种 与HashTable完全不同的加锁策略提供更⾼效的并发性和伸缩性。

ConcurrentHashMap提供了⼀种粒度更细的加锁机制来实现在多线程下更⾼的性 能，这种机制叫分段锁(Lock Striping)。

提供的优点是：在并发环境下将实现更⾼的吞吐量，⽽在单线程环境下只损失⾮常 ⼩的性能。 可以这样理解分段锁，就是将数据分段，对每⼀段数据分配⼀把锁。当⼀个线程占 ⽤锁访问其中⼀个段数据的时候，其他段的数据也能被其他线程访问。 有些⽅法需要跨段，⽐如size()、isEmpty()、containsValue()，它们可能需要锁定 整个表⽽⽽不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，⼜按顺序释 放所有段的锁。

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment 是⼀种可重⼊锁ReentrantLock，HashEntry则⽤于存储键值对数据。 ⼀个ConcurrentHashMap⾥包含⼀个Segment数组，Segment的结构和HashMap 类似，是⼀种数组和链表结构， ⼀个Segment⾥包含⼀个HashEntry数组，每个 HashEntry是⼀个链表结构（同HashMap⼀样，它也会在⻓度达到8的时候转化为 红⿊树）的元素， 每个Segment守护者⼀个HashEntry数组⾥的元素，当对 HashEntry数组的数据进⾏修改时，必须⾸先获得它对应的Segment锁。

在使用并发集合与使用非线程安全的集合类完全相同。首先以ConcurrentHashMap为例：

Map<String, String> map = new ConcurrentHashMap<>();
// 在不同的线程读写:
map.put("A", "1");
map.put("B", "2");
map.get("A", "1");

因为所有的同步和加锁的逻辑都在集合内部实现，对外部调用者来说，只需要正常按接口引用，其他代码和原来的非线程安全代码完全一样。即当我们需要多线程访问时，把：

Map<String, String> map = new HashMap<>();

改为：

Map<String, String> map = new ConcurrentHashMap<>();

就可以了。

java.util.Collections工具类还提供了一个旧的线程安全集合转换器，可以这么用：

Map unsafeMap = new HashMap();
Map threadSafeMap = Collections.synchronizedMap(unsafeMap);

但是它实际上是用一个包装类包装了非线程安全的Map，然后对所有读写方法都用synchronized加锁，这样获得的线程安全集合的性能比java.util.concurrent集合要低很多，所以不推荐使用。

ConcurrentNavigableMap接⼝继承了NavigableMap接⼝，这个接⼝提供了针对给 定搜索⽬标返回最接近匹配项的导航⽅法。ConcurrentNavigableMap接⼝的主要实现类是ConcurrentSkipListMap类。从名字 上来看，它的底层使⽤的是跳表（SkipList）的数据结构。

关于跳表的数据结构这 ⾥不做太多介绍，它是⼀种”空间换时间“的数据结构，可以使⽤CAS来保证并发安 全性。

ConcurrentHashMap的结构

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

ConcurrentHashMap的初始化

ConcurrentHashMap初始化方法是通过initialCapacity、loadFactor和concurrencyLevel等几个 参数来初始化segment数组、段偏移量segmentShift、段掩码segmentMask和每个segment里的 HashEntry数组来实现的。

• 初始化segments数组

下初始化segments数组的源代码

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

注意 concurrencyLevel的最大值是65535，这意味着segments数组的长度最大为65536， 对应的二进制是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

• 初始化每个segment

输入参数initialCapacity是ConcurrentHashMap的初始化容量，loadfactor是每个segment的负 载因子，在构造方法里需要通过这两个参数来初始化数组中的每个segment。

上面代码中的变量cap就是segment里HashEntry数组的长度，它等于initialCapacity除以ssize 的倍数c，如果c大于1，就会取大于等于c的2的N次方值，所以cap不是1，就是2的N次方。 segment的容量threshold＝（int）cap*loadFactor，默认情况下initialCapacity等于16，loadfactor等于 0.75，通过运算cap等于1，threshold等于零

定位Segment

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

    private static int hash(int h) {
        h += (h << 15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h << 3);
        h ^= (h >>> 6);
        h += (h << 2) + (h << 14);
        return h ^ (h >>> 16);
    }

之所以进行再散列，目的是减少散列冲突，使元素能够均匀地分布在不同的Segment上， 从而提高容器的存取效率。假如散列的质量差到极点，那么所有的元素都在一个Segment中， 不仅存取元素缓慢，分段锁也会失去意义。笔者做了一个测试，不通过再散列而直接执行散列 计算。

System.out.println(Integer.parseInt("0001111", 2) & 15);
System.out.println(Integer.parseInt("0011111", 2) & 15);
System.out.println(Integer.parseInt("0111111", 2) & 15);
System.out.println(Integer.parseInt("1111111", 2) & 15);

计算后输出的散列值全是15，通过这个例子可以发现，如果不进行再散列，散列冲突会非 常严重，因为只要低位一样，无论高位是什么数，其散列值总是一样。我们再把上面的二进制 数据进行再散列后结果如下（为了方便阅读，不足32位的高位补了0，每隔4位用竖线分割下）。

0100｜0111｜0110｜0111｜1101｜1010｜0100｜1110
1111｜0111｜0100｜0011｜0000｜0001｜1011｜1000
0111｜0111｜0110｜1001｜0100｜0110｜0011｜1110
1000｜0011｜0000｜0000｜1100｜1000｜0001｜1010

可以发现，每一位的数据都散列开了，通过这种再散列能让数字的每一位都参加到散列 运算当中，从而减少散列冲突。ConcurrentHashMap通过以下散列算法定位segment。

final Segment segmentFor(int hash) { return segments[(hash >>> segmentShift) & segmentMask]; }

默认情况下segmentShift为28，segmentMask为15，再散列后的数最大是32位二进制数据， 向右无符号移动28位，意思是让高4位参与到散列运算中，（hash>>>segmentShift） &segmentMask的运算结果分别是4、15、7和8，可以看到散列值没有发生冲突。

ConcurrentHashMap的操作

• get操作

Segment的get操作实现非常简单和高效。先经过一次再散列，然后使用这个散列值通过散 列运算定位到Segment，再通过散列算法定位到元素

public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
}

get操作的高效之处在于整个get过程不需要加锁，除非读到的值是空才会加锁重读。我们 知道HashTable容器的get方法是需要加锁的，那么ConcurrentHashMap的get操作是如何做到不 加锁的呢？原因是它的get方法里将要使用的共享变量都定义成volatile类型，如用于统计当前 Segement大小的count字段和用于存储值的HashEntry的value。定义成volatile的变量，能够在线 程之间保持可见性，能够被多线程同时读，并且保证不会读到过期的值，但是只能被单线程写 （有一种情况可以被多线程写，就是写入的值不依赖于原值），在get操作里只需要读不需要写 共享变量count和value，所以可以不用加锁。之所以不会读到过期的值，是因为根据Java内存模 型的happen before原则，对volatile字段的写入操作先于读操作，即使两个线程同时修改和获取 volatile变量，get操作也能拿到最新的值，这是用volatile替换锁的经典应用场景。

transient volatile int count;

volatile V value;

在定位元素的代码里我们可以发现，定位HashEntry和定位Segment的散列算法虽然一样， 都与数组的长度减去1再相“与”，但是相“与”的值不一样，定位Segment使用的是元素的 hashcode通过再散列后得到的值的高位，而定位HashEntry直接使用的是再散列后的值。其目的 是避免两次散列后的值一样，虽然元素在Segment里散列开了，但是却没有在HashEntry里散列 开。

hash >>> segmentShift) & segmentMask // 定位Segment所使用的hash算法
 
int index = hash & (tab.length - 1); // 定位HashEntry所使用的hash算法

• put操作

由于put方法里需要对共享变量进行写入操作，所以为了线程安全，在操作共享变量时必 须加锁。put方法首先定位到Segment，然后在Segment里进行插入操作。插入操作需要经历两个 步骤，第一步判断是否需要对Segment里的HashEntry数组进行扩容，第二步定位添加元素的位 置，然后将其放在HashEntry数组里。

（1）是否需要扩容 在插入元素前会先判断Segment里的HashEntry数组是否超过容量（threshold），如果超过阈 值，则对数组进行扩容。值得一提的是，Segment的扩容判断比HashMap更恰当，因为HashMap 是在插入元素后判断元素是否已经到达容量的，如果到达了就进行扩容，但是很有可能扩容 之后没有新元素插入，这时HashMap就进行了一次无效的扩容。 （2）如何扩容 在扩容的时候，首先会创建一个容量是原来容量两倍的数组，然后将原数组里的元素进 行再散列后插入到新的数组里。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而只 对某个segment进行扩容。

• size操作

如果要统计整个ConcurrentHashMap里元素的大小，就必须统计所有Segment里元素的大小 后求和。Segment里的全局变量count是一个volatile变量，那么在多线程场景下，是不是直接把 所有Segment的count相加就可以得到整个ConcurrentHashMap大小了呢？

不是的，虽然相加时 可以获取每个Segment的count的最新值，但是可能累加前使用的count发生了变化，那么统计结 果就不准了。所以，最安全的做法是在统计size的时候把所有Segment的put、remove和clean方法 全部锁住，但是这种做法显然非常低效。

因为在累加count操作过程中，之前累加过的count发生变化的几率非常小，所以 ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小，如 果统计的过程中，容器的count发生了变化，则再采用加锁的方式来统计所有Segment的大小。

那么ConcurrentHashMap是如何判断在统计的时候容器是否发生了变化呢？使用modCount 变量，在put、remove和clean方法里操作元素前都会将变量modCount进行加1，那么在统计size 前后比较modCount是否发生变化，从而得知容器的大小是否发生变化。

三、并发list

获取线程安全的List我们可以通过Vector、Collections.synchronizedList()方法和CopyOnWriteArrayList三种方式

读少写多的情况下，推荐使用Collections.synchronizedList()的方式

读多写少的情况下，推荐使用CopyOnWriteArrayList方

什么是CopyOnWrite机制， CopyOnWrite是计算机设计领域中的⼀种优化策略，也是⼀种在并发场景下常⽤的 设计思想——写⼊时复制思想。

那什么是写⼊时复制思想呢？就是当有多个调⽤者同时去请求⼀个资源数据的时 候，有⼀个调⽤者出于某些原因需要对当前的数据源进⾏修改，这个时候系统将会 复制⼀个当前数据源的副本给调⽤者修改。

CopyOnWrite容器即写时复制的容器,当我们往⼀个容器中添加元素的时候，不直接 往容器中添加，⽽是将当前容器进⾏copy，复制出来⼀个新的容器，然后向新容器 中添加我们需要的元素，最后将原容器的引⽤指向新容器。

这样做的好处在于，我们可以在并发的场景下对容器进⾏"读操作"⽽不需要"加 锁"，从⽽达到读写分离的⽬的。从JDK 1.5 开始Java并发包⾥提供了两个使⽤ CopyOnWrite机制实现的并发容器 ，分别是CopyOnWriteArrayList和 CopyOnWriteArraySet

优点： CopyOnWriteArrayList经常被⽤于“读多写少”的并发场景，是因为 CopyOnWriteArrayList⽆需任何同步措施，⼤⼤增强了读的性能。在Java中遍历线 程⾮安全的List(如：ArrayList和 LinkedList)的时候，若中途有别的线程对List容器 进⾏修改，那么会抛出ConcurrentModificationException异常。 CopyOnWriteArrayList由于其"读写分离"，遍历和修改操作分别作⽤在不同的List容 器，所以在使⽤迭代器遍历的时候，则不会抛出异常。

缺点： 第⼀个缺点是CopyOnWriteArrayList每次执⾏写操作都会将原容器进⾏拷⻉ 了⼀份，数据量⼤的时候，内存会存在较⼤的压⼒，可能会引起频繁Full GC（ZGC因为没有使⽤Full GC）。⽐如这些对象占⽤的内存⽐较⼤200M左右， 那么再写⼊100M数据进去，内存就会多占⽤300M。 第⼆个缺点是CopyOnWriteArrayList由于实现的原因，写和读分别作⽤在不同新⽼ 容器上，在写操作执⾏过程中，读不会阻塞，但读取到的却是⽼容器的数据。

现在我们来看⼀下CopyOnWriteArrayList的add操作源码，它的逻辑很清晰，就是 先把原容器进⾏copy，然后在新的副本上进⾏“写操作”，最后再切换引⽤，在此过 程中是加了锁的。

public boolean add(E e) {
 // ReentrantLock加锁，保证线程安全
 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;
 // 将原容器引⽤指向新副本
 setArray(newElements);
 return true;
 } finally {
 // 解锁
 lock.unlock();
 }
}

我们再来看⼀下remove操作的源码，remove的逻辑是将要remove元素之外的其他 元素拷⻉到新的副本中，然后切换引⽤，再将原容器的引⽤指向新的副本中，因为 remove操作也是“写操作”所以也是要加锁的。

public E remove(int index) {
 // 加锁
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
 Object[] elements = getArray();
 int len = elements.length;
 E oldValue = get(elements, index);
 int numMoved = len - index - 1;
 if (numMoved == 0)
 // 如果要删除的是列表末端数据，拷⻉前len-1个数据到新副本上，再切换引⽤
 setArray(Arrays.copyOf(elements, len - 1));
 else {
 // 否则，将除要删除元素之外的其他元素拷⻉到新副本中，并切换引⽤
 Object[] newElements = new Object[len - 1];
 System.arraycopy(elements, 0, newElements, 0, index);
 System.arraycopy(elements, index + 1, newElements, index,
 numMoved);
 setArray(newElements);
 }
 return oldValue;
 } finally {
 // 解锁
 lock.unlock();
 }
 }

我们再来看看CopyOnWriteArrayList效率最⾼的读操作的源码

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

由上可⻅“读操作”是没有加锁，直接读取。

四、并发set

Set的三个子类分别是：HaseSet、TreeSet、LinkedHashSet.这三个都是线程不安全的，底层其实都是Map的，Map是key-value键值对出现的。

Set集合怎么实现线程安全？

方案一：

和list一样，使用Colletcions这个工具类syn方法类创建个线程安全的set.

Set<String> synSet = Collections.synchronizedSet(new HashSet<>());

方案二：

使用JUC包里面的CopyOnWriteArraySet

Set<String> copySet = new CopyOnWriteArraySet<>();

另外JDK提供了ConcurrentSkipListSet，是线程安全的有序的集合。底层是使⽤ ConcurrentSkipListMap实现。

1.CopyOnWriteArraySet：无序，添加时内存占有率高，弱一致性。

2.ConcurrentSkipListSet：有序，需要维护索引，弱一致性。

五、并发queue

1、非阻塞队列

在并发编程中，有时候需要使用线程安全的队列。如果要实现一个线程安全的队列有两 种方式：一种是使用阻塞算法，另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁 （入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。非阻塞的实现方 式则可以使用循环CAS的方式来实现，jdk是如何使用非阻 塞的方式来实现线程安全队列ConcurrentLinkedQueue的？

其实ConcurrentLinkedDeque和ConcurrentLinkedQueue，这两个类是使⽤CAS算法来实现线程安全的非租塞队列。

1.1、ConcurrentLinkedQueue

ConcurrentLinkedQueue 的主要特点包括：

线程安全：ConcurrentLinkedQueue 是线程安全的，可以被多个线程同时操作而无需额外的同步措施。它使用原子操作和无锁算法来保证并发访问的安全性。
非阻塞算法：ConcurrentLinkedQueue 使用非阻塞算法，不会出现线程被阻塞等待队列操作的情况。这使得它具有良好的并发性能和可伸缩性。
无界队列：ConcurrentLinkedQueue 是一个无界队列，它不会限制队列的容量。可以根据需求添加任意数量的元素。
FIFO顺序：ConcurrentLinkedQueue 采用先进先出（FIFO）的顺序，即最先插入的元素最先被移除。
迭代支持：ConcurrentLinkedQueue 提供了迭代器（Iterator）来遍历队列中的元素。迭代器遍历时不会抛出 ConcurrentModificationException 异常，并且可以在并发环境下安全使用。

ConcurrentLinkedQueue 提供了常见的队列操作，如插入元素、获取头部元素、移除头部元素等。一些常用的方法包括 offer()、poll()、peek() 等。需要注意的是，ConcurrentLinkedQueue 并不保证队列的一致性排序。在高度并发的情况下，可能会出现一些不确定的元素顺序。如果需要有序性，可以考虑使用 PriorityQueue 或其他有序队列实现。总结起来，ConcurrentLinkedQueue 是一个高效的线程安全非阻塞队列实现，适用于并发环境下的多线程操作。它的设计目标是提供高性能和可伸缩性，适用于高度并发的场景。

public class Main {
    public static void main(String[] args) {
      try{
          Myservice myservice=new Myservice();
          ThreadA a=new ThreadA(myservice);
          ThreadB b=new ThreadB(myservice);
 
          a.start();
          b.start();
          a.join();
          b.join();
          System.out.println(myservice.queue.size());
      }catch (InterruptedException e){
          e.printStackTrace();
      }
    }
}
class Myservice{
    public ConcurrentLinkedQueue queue=new ConcurrentLinkedQueue<>();
}
class ThreadA extends Thread{
    private Myservice myservice;
    public ThreadA(Myservice myservice){
        super();
        this.myservice=myservice;
    }
 
    @Override
    public void run() {
        for (int i = 0; i < 50; i++) {
            myservice.queue.add("threadA"+(i+1));
        }
    }
}
class ThreadB extends Thread{
    private Myservice myservice;
    public ThreadB(Myservice myservice){
        super();
        this.myservice=myservice;
    }
 
    @Override
    public void run() {
        for (int i = 0; i < 50; i++) {
            myservice.queue.add("threadB"+(i+1));
        }
    }
}

ConcurrentLinkedQueue有如下常用的方法：

poll()：没有获得数据时返回null，获得数据时则移除表头进行返回

element()：没有获得数据时出现NoSuchElementException异常，获得数据时则不移除表头，并将表头进行返回

peek()：没有获得数据时返回null，获得数据时则不移除表头，并将表头进行返回

1.2、ConcurrentLinkedDeque

是 Java 中的一个并发安全的双向链表实现，它是 Deque 接口的一个实现类。ConcurrentLinkedDeque 提供了高效的并发操作，可以在多线程环境下安全地进行插入、删除和访问元素的操作ConcurrentLinkedDeque 的特点如下：

无界容量：ConcurrentLinkedDeque 是一个无界容量的双向链表，可以根据需要动态地增加元素。

非阻塞算法：ConcurrentLinkedDeque 内部使用了非阻塞算法，不依赖于锁机制，因此可以在并发环境下提供更好的性能。

双向链表：ConcurrentLinkedDeque 支持从两端进行插入和删除元素的操作，可以在头部或尾部插入、删除和访问元素。

线程安全：ConcurrentLinkedDeque 是线程安全的，多线程可以同时进行操作而不会导致数据不一致的问题。它通过使用 CAS（Compare and Swap）操作和无锁算法来实现线程安全性。

迭代器支持：ConcurrentLinkedDeque 提供了迭代器，可以安全地遍历集合中的元素。迭代器遍历时不会抛出 ConcurrentModificationException 异常。

ConcurrentLinkedDeque 提供了一系列的方法，包括添加元素、删除元素、获取元素以及判断集合是否为空等操作。一些常用的方法有：

addFirst(E e) 和 addLast(E e)：在链表的头部或尾部添加指定元素。

removeFirst() 和 removeLast()：从链表的头部或尾部删除并返回元素。

peekFirst() 和 peekLast()：返回链表的头部或尾部的元素，但不删除。

isEmpty()：判断链表是否为空。

size()：返回链表中的元素个数。

需要注意的是，ConcurrentLinkedDeque 不允许存储 null 元素。由于 ConcurrentLinkedDeque 是线程安全的，它适用于多线程环境下需要高效并发操作的场景。

public class Main {
    public static void main(String[] args) throws InterruptedException {
     Myservice myservice=new Myservice();
     ThreadA aFirst=new ThreadA(myservice);
     ThreadA bFirst=new ThreadA(myservice);
     ThreadB aLast=new ThreadB(myservice);
     ThreadB bLast=new ThreadB(myservice);
     aFirst.start();
     Thread.sleep(1000);
     aLast.start();
     Thread.sleep(1000);
 
     bFirst.start();
     Thread.sleep(1000);
     bLast.start();
    }
}
class Myservice{
    public ConcurrentLinkedDeque queue=new ConcurrentLinkedDeque<>();
    public Myservice(){
        for (int i = 0; i < 4; i++) {
            queue.add("String"+(i+1));
        }
    }
 
}
class ThreadA extends Thread{
    private Myservice myservice;
    public ThreadA(Myservice myservice){
        super();
        this.myservice=myservice;
    }
 
    @Override
    public void run() {
        System.out.println("value="+myservice.queue.pollLast()+"queue.size()="+myservice.queue.size() );
    }
}
class ThreadB extends Thread{
    private Myservice myservice;
    public ThreadB(Myservice myservice){
        super();
        this.myservice=myservice;
    }
 
    @Override
    public void run() {
        System.out.println("value="+myservice.queue.pollFirst()+"queue.size()="+myservice.queue.size() );
    }
}

1.3、ConcurrentLinkedQueue实现细节

ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规 则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部；当我们获取一个元 素时，它会返回队列头部的元素。它采用了“wait-free”算法（即CAS算法）来实现，该算法在 Michael&Scott算法上进行了一些修改。

通过ConcurrentLinkedQueue的类图来分析一下它的结构

ConcurrentLinkedQueue由head节点和tail节点组成，每个节点（Node）由节点元素（item）和 指向下一个节点（next）的引用组成，节点与节点之间就是通过这个next关联起来，从而组成一 张链表结构的队列。默认情况下head节点存储的元素为空，tail节点等于head节点。

private transient volatile Node tail = head;

入队列的过程

入队列就是将入队节点添加到队列的尾部。为了方便理解入队时队列的变化，以及head节 点和tail节点的变化，这里以一个示例来展开介绍。

假设我们想在一个队列中依次插入4个节 点，为了帮助大家理解，每添加一个节点就做了一个队列的快照图，如图6-4所示。 图6-4所示的过程如下。

添加元素1。队列更新head节点的next节点为元素1节点。又因为tail节点默认情况下等于 head节点，所以它们的next节点都指向元素1节点。

添加元素2。队列首先设置元素1节点的next节点为元素2节点，然后更新tail节点指向元素 2节点

添加元素3，设置tail节点的next节点为元素3节点。

添加元素4，设置元素3的next节点为元素4节点，然后将tail节点指向元素4节点。

通过调试入队过程并观察head节点和tail节点的变化，发现入队主要做两件事情：第一是 将入队节点设置成当前队列尾节点的下一个节点；第二是更新tail节点，如果tail节点的next节 点不为空，则将入队节点设置成tail节点，如果tail节点的next节点为空，则将入队节点设置成 tail的next节点，所以tail节点不总是尾节点（理解这一点对于我们研究源码会非常有帮助）。

通过对上面的分析，我们从单线程入队的角度理解了入队过程，但是多个线程同时进行 入队的情况就变得更加复杂了，因为可能会出现其他线程插队的情况。如果有一个线程正在 入队，那么它必须先获取尾节点，然后设置尾节点的下一个节点为入队节点，但这时可能有另 外一个线程插队了，那么队列的尾节点就会发生变化，这时当前线程要暂停入队操作，然后重 新获取尾节点。让我们再通过源码来详细分析一下它是如何使用CAS算法来入队的

    public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
// 入队前，创建一个入队节点
        Node<E> n = new Node<E>(e);
        retry:
// 死循环，入队不成功反复入队。
        for (;;) {
// 创建一个指向tail节点的引用
            Node<E> t = tail;
// p用来表示队列的尾节点，默认情况下等于tail节点。
            Node<E> p = t;
            for (int hops = 0; ; hops++) {
// 获得p节点的下一个节点。
                Node<E> next = succ(p);
// next节点不为空，说明p不是尾节点，需要更新p后在将它指向next节点
                if (next != null) {
// 循环了两次及其以上，并且当前节点还是不等于尾节点
                    if (hops > HOPS && t != tail)
                        continue retry;
                    p = next;
                }
// 如果p是尾节点，则设置p节点的next节点为入队节点。
                else if (p.casNext(null, n)) {
/*如果tail节点有大于等于1个next节点，则将入队节点设置成tail节点，
更新失败了也没关系，因为失败了表示有其他线程成功更新了tail节点*/
                    if (hops >= HOPS)
                        casTail(t, n); // 更新tail节点，允许失败
                    return true;
                }
// p有next节点,表示p的next节点是尾节点，则重新设置p节点
                else {
                    p = succ(p);
                }
            }
        }
    }

从源代码角度来看，整个入队过程主要做两件事情：第一是定位出尾节点；第二是使用 CAS算法将入队节点设置成尾节点的next节点，如不成功则重试。

定位尾节点

tail节点并不总是尾节点，所以每次入队都必须先通过tail节点来找到尾节点。尾节点可能 是tail节点，也可能是tail节点的next节点。代码中循环体中的第一个if就是判断tail是否有next节 点，有则表示next节点可能是尾节点。获取tail节点的next节点需要注意的是p节点等于p的next 节点的情况，只有一种可能就是p节点和p的next节点都等于空，表示这个队列刚初始化，正准 备添加节点，所以需要返回head节点。获取p节点的next节点代码如下。

final Node succ(Node p) { Node next = p.getNext(); return (p == next) head : next; }

设置入队节点为尾节点

p.casNext（null，n）方法用于将入队节点设置为当前队列尾节点的next节点，如果p是null， 表示p是当前队列的尾节点，如果不为null，表示有其他线程更新了尾节点，则需要重新获取当 前队列的尾节点

HOPS的设计意图

上面分析过对于先进先出的队列入队所要做的事情是将入队节点设置成尾节点，doug lea 写的代码和逻辑还是稍微有点复杂。那么，我用以下方式来实现是否可行？

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        Node<E> n = new Node<E>(e);
        for (;;) {
            Node<E> t = tail;
            if (t.casNext(null, n) && casTail(t, n)) {
                return true;
            }
        }
    }

让tail节点永远作为队列的尾节点，这样实现代码量非常少，而且逻辑清晰和易懂。但是， 这么做有个缺点，每次都需要使用循环CAS更新tail节点。如果能减少CAS更新tail节点的次 数，就能提高入队的效率，所以doug lea使用hops变量来控制并减少tail节点的更新频率，并不 是每次节点入队后都将tail节点更新成尾节点，而是当tail节点和尾节点的距离大于等于常量 HOPS的值（默认等于1）时才更新tail节点，tail和尾节点的距离越长，使用CAS更新tail节点的次 数就会越少，但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长，因为 循环体需要多循环一次来定位出尾节点，但是这样仍然能提高入队的效率，因为从本质上来 看它通过增加对volatile变量的读操作来减少对volatile变量的写操作，而对volatile变量的写操 作开销要远远大于读操作，所以入队效率会有所提升。

private static final int HOPS = 1;

注意 入队方法永远返回true，所以不要通过返回值判断入队是否成功

出队列

出队列的就是从队列里返回一个节点元素，并清空该节点对元素的引用。让我们通过每 个节点出队的快照来观察一下head节点的变化，如图所示。

从图中可知，并不是每次出队时都更新head节点，当head节点里有元素时，直接弹出head 节点里的元素，而不会更新head节点。只有当head节点里没有元素时，出队操作才会更新head 节点。这种做法也是通过hops变量来减少使用CAS更新head节点的消耗，从而提高出队效率。 让我们再通过源码来深入分析下出队过程。

    public E poll() {
        Node<E> h = head;
// p表示头节点，需要出队的节点
        Node<E> p = h;
        for (int hops = 0;; hops++) {
// 获取p节点的元素
            E item = p.getItem();
// 如果p节点的元素不为空，使用CAS设置p节点引用的元素为null,
// 如果成功则返回p节点的元素。
            if (item != null && p.casItem(item, null)) {
                if (hops >= HOPS) {
// 将p节点下一个节点设置成head节点
                    Node<E> q = p.getNext();
                    updateHead(h, (q != null) q : p);
                }
                return item;
            }
// 如果头节点的元素为空或头节点发生了变化，这说明头节点已经被另外
// 一个线程修改了。那么获取p节点的下一个节点
            Node<E> next = succ(p);
// 如果p的下一个节点也为空，说明这个队列已经空了
            if (next == null) {
// 更新头节点。
                updateHead(h, p);
                break;
            }
// 如果下一个元素不为空，则将头节点的下一个节点设置成头节点
            p = next;
        }
        return null;
    }

首先获取头节点的元素，然后判断头节点元素是否为空，如果为空，表示另外一个线程已 经进行了一次出队操作将该节点的元素取走，如果不为空，则使用CAS的方式将头节点的引 用设置成null，如果CAS成功，则直接返回头节点的元素，如果不成功，表示另外一个线程已经 进行了一次出队操作更新了head节点，导致元素发生了变化，需要重新获取头节点

2、阻塞队列

我们假设⼀种场景，⽣产者⼀直⽣产资源，消费者⼀直消费资源，资源存储在⼀个 缓冲池中，⽣产者将⽣产的资源存进缓冲池中，消费者从缓冲池中拿到资源进⾏消 费，这就是⼤名鼎鼎的⽣产者-消费者模式。

该模式能够简化开发过程，⼀⽅⾯消除了⽣产者类与消费者类之间的代码依赖性， 另⼀⽅⾯将⽣产数据的过程与使⽤数据的过程解耦简化负载。 我们⾃⼰coding实现这个模式的时候，因为需要让多个线程操作共享变量（即资 源），所以很容易引发线程安全问题，造成重复消费和死锁，尤其是⽣产者和消费 者存在多个的情况。另外，当缓冲池空了，我们需要阻塞消费者，唤醒⽣产者；当 缓冲池满了，我们需要阻塞⽣产者，唤醒消费者，这些个等待-唤醒逻辑都需要⾃ ⼰实现。

这么容易出错的事情，JDK当然帮我们做啦，这就是阻塞队列(BlockingQueue)， 你只管往⾥⾯存、取就⾏，⽽不⽤担⼼多线程环境下存、取共享变量的线程安全问题。

BlockingQueue是Java util.concurrent包下重要的数据结构，区别于普通的队 列，BlockingQueue提供了线程安全的队列访问⽅式，并发包下很多⾼级同 步类的实现都是基于BlockingQueue实现的。

BlockingQueue⼀般⽤于⽣产者-消费者模式，⽣产者是往队列⾥添加元素的线程， 消费者是从队列⾥拿元素的线程。BlockingQueue就是存放元素的容器。

支持两个附加操作的队列。这两个附加的操作支持阻塞 的插入和移除方法。

1）支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不 满。

2）支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空。

在阻塞队列不可用时，这两个附加操作提供了4种处理方式

抛出异常：当队列满时，如果再往队列里插入元素，会抛出IllegalStateException（"Queue full"）异常。当队列空时，从队列里获取元素会抛出NoSuchElementException异常。

返回特殊值：当往队列插入元素时，会返回元素是否插入成功，成功返回true。如果是移 除方法，则是从队列里取出一个元素，如果没有则返回null。

一直阻塞：当阻塞队列满时，如果生产者线程往队列里put元素，队列会一直阻塞生产者 线程，直到队列可用或者响应中断退出。当队列空时，如果消费者线程从队列里take元素，队 列会阻塞住消费者线程，直到队列不为空。

超时退出：当阻塞队列满时，如果生产者线程往队列里插入元素，队列会阻塞生产者线程 一段时间，如果超过了指定的时间，生产者线程就会退出。

这两个附加操作的4种处理方式不方便记忆，所以我找了一下这几个方法的规律。put和 take分别尾首含有字母t，offer和poll都含有字母o。

如果是无界阻塞队列，队列不可能会出现满的情况，所以使用put或offer方法永 远不会被阻塞，而且使用offer方法时，该方法永远返回true

注意：

• 不能往阻塞队列中插⼊null,会抛出空指针异常。
• 可以访问阻塞队列中的任意元素，调⽤remove(o)可以将队列之中的特定对象 移除，但并不⾼效，尽量避免使⽤

jdk提供了7中常见的阻塞队列，如下。

ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。

LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。

PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。

DelayQueue：一个使用优先级队列实现的无界阻塞队列。

SynchronousQueue：一个不存储元素的阻塞队列。

LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。

LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列

ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。

ArrayBlockingQueue是一个用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原 则对元素进行排序。 默认情况下不保证线程公平的访问队列，所谓公平访问队列是指阻塞的线程，可以按照 阻塞的先后顺序访问队列，即先阻塞线程先访问队列。非公平性是对先等待的线程是非公平 的，当队列可用时，阻塞的线程都可以争夺访问队列的资格，有可能先阻塞的线程最后才访问 队列。为了保证公平性，通常会降低吞吐量。我们可以使用以下代码创建一个公平的阻塞队 列。

ArrayBlockingQueue fairQueue = new ArrayBlockingQueue(1000,true);

访问者的公平性是使用可重入锁实现的，代码如下。

public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
lock = new ReentrantLock(fair);
notEmpty = lock.newCondition();
notFull = lock.newCondition();
}

LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。

由链表结构组成的有界阻塞队列。内部结构是链表，具有链表的特性。默认队列的 ⼤⼩是 Integer.MAX_VALUE ，也可以指定⼤⼩。此队列按照先进先出的原则对元素 进⾏排序

PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。

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

DelayQueue：一个使用优先级队列实现的无界阻塞队列。

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

• 缓存系统的设计：可以用DelayQueue保存缓存元素的有效期，使用一个线程循环查询 DelayQueue，一旦能从DelayQueue中获取元素时，表示缓存有效期到了。
• 定时任务调度：使用DelayQueue保存当天将会执行的任务和执行时间，一旦从 DelayQueue中获取到任务就开始执行，比如TimerQueue就是使用DelayQueue实现的

（1）如何实现Delayed接口 DelayQueue队列的元素必须实现Delayed接口。我们可以参考ScheduledThreadPoolExecutor 里ScheduledFutureTask类的实现，一共有三步。

第一步：在对象创建的时候，初始化基本数据。使用time记录当前对象延迟到什么时候可 以使用，使用sequenceNumber来标识元素在队列中的先后顺序。代码如下。

private static final AtomicLong sequencer = new AtomicLong(0);
ScheduledFutureTask(Runnable r, V result, long ns, long period) {
ScheduledFutureTask(Runnable r, V result, long ns, long period) {
super(r, result);
this.time = ns;
this.period = period;
this.sequenceNumber = sequencer.getAndIncrement();
}

第二步：实现getDelay方法，该方法返回当前元素还需要延时多长时间，单位是纳秒，代码 如下。

public long getDelay(TimeUnit unit) {
return unit.convert(time - now(), TimeUnit.NANOSECONDS);
}

通过构造函数可以看出延迟时间参数ns的单位是纳秒，自己设计的时候最好使用纳秒，因 为实现getDelay()方法时可以指定任意单位，一旦以秒或分作为单位，而延时时间又精确不到 纳秒就麻烦了。使用时请注意当time小于当前时间时，getDelay会返回负数。

第三步：实现compareTo方法来指定元素的顺序。例如，让延时时间最长的放在队列的末 尾。实现代码如下

public int compareTo(Delayed other) {
        if (other == this) // compare zero ONLY if same object
            return 0;
        if (other instanceof ScheduledFutureTask) {
            ScheduledFutureTask<> x = (ScheduledFutureTask<>)other;
            long diff = time - x.time;
            if (diff < 0)
                return -1;
            else if (diff > 0)
                return 1;
            else if (sequenceNumber < x.sequenceNumber)
                return -1;
            else
                return 1;
        }
        long d = (getDelay(TimeUnit.NANOSECONDS) -
                other.getDelay(TimeUnit.NANOSECONDS));
        return (d == 0) 0 : ((d < 0) -1 : 1);
    }

（2）如何实现延时阻塞队列 延时阻塞队列的实现很简单，当消费者从队列里获取元素时，如果元素没有达到延时时 间，就阻塞当前线程。

long delay = first.getDelay(TimeUnit.NANOSECONDS);
        if (delay <= 0)
            return q.poll();
        else if (leader != null)
            available.await();
        else {
            Thread thisThread = Thread.currentThread();
            leader = thisThread;
            try {
                available.awaitNanos(delay);
            } finally {
                if (leader == thisThread)
                    leader = null;
            }
        }

代码中的变量leader是一个等待获取队列头部元素的线程。如果leader不等于空，表示已 经有线程在等待获取队列的头元素。所以，使用await()方法让当前线程等待信号。如果leader 等于空，则把当前线程设置成leader，并使用awaitNanos()方法让当前线程等待接收信号或等 待delay时间。

SynchronousQueue：一个不存储元素的阻塞队列。

SynchronousQueue是一个不存储元素的阻塞队列。每一个put操作必须等待一个take操作， 否则不能继续添加元素。 它支持公平访问队列。默认情况下线程采用非公平性策略访问队列。使用以下构造方法 可以创建公平性访问的SynchronousQueue，如果设置为true，则等待的线程会采用先进先出的 顺序访问队列

public SynchronousQueue(boolean fair) { transferer = fair new TransferQueue() : new TransferStack(); }

SynchronousQueue可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费 者线程。队列本身并不存储任何元素，非常适合传递性场景。SynchronousQueue的吞吐量高于 LinkedBlockingQueue和ArrayBlockingQueue。

LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。

LinkedTransferQueue是一个由链表结构组成的无界阻塞TransferQueue队列。相对于其他阻 塞队列，LinkedTransferQueue多了tryTransfer和transfer方法。

（1）transfer方法 如果当前有消费者正在等待接收元素（消费者使用take()方法或带时间限制的poll()方法 时），transfer方法可以把生产者传入的元素立刻transfer（传输）给消费者。如果没有消费者在等 待接收元素，transfer方法会将元素存放在队列的tail节点，并等到该元素被消费者消费了才返 回。transfer方法的关键代码如下

Node pred = tryAppend(s, haveData);
 
return awaitMatch(s, pred, e, (how == TIMED), nanos);

第一行代码是试图把存放当前元素的s节点作为tail节点。第二行代码是让CPU自旋等待 消费者消费元素。因为自旋会消耗CPU，所以自旋一定的次数后使用Thread.yield()方法来暂停 当前正在执行的线程，并执行其他线程。

（2）tryTransfer方法 tryTransfer方法是用来试探生产者传入的元素是否能直接传给消费者。如果没有消费者等 待接收元素，则返回false。和transfer方法的区别是tryTransfer方法无论消费者是否接收，方法 立即返回，而transfer方法是必须等到消费者消费了才返回。

对于带有时间限制的tryTransfer（E e，long timeout，TimeUnit unit）方法，试图把生产者传入 的元素直接传给消费者，但是如果没有消费者消费该元素则等待指定的时间再返回，如果超 时还没消费元素，则返回false，如果在超时时间内消费了元素，则返回true。

LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列

LinkedBlockingDeque是一个由链表结构组成的双向阻塞队列。所谓双向队列指的是可以 从队列的两端插入和移出元素。双向队列因为多了一个操作队列的入口，在多线程同时入队 时，也就减少了一半的竞争。相比其他的阻塞队列，LinkedBlockingDeque多了addFirst、 addLast、offerFirst、offerLast、peekFirst和peekLast等方法，以First单词结尾的方法，表示插入、 获取（peek）或移除双端队列的第一个元素。以Last单词结尾的方法，表示插入、获取或移除双 端队列的最后一个元素。另外，插入方法add等同于addLast，移除方法remove等效于 removeFirst。但是take方法却等同于takeFirst，不知道是不是JDK的bug，使用时还是用带有First 和Last后缀的方法更清楚。

在初始化LinkedBlockingDeque时可以设置容量防止其过度膨胀。另外，双向阻塞队列可以 运用在“工作窃取”模式中。

3、阻塞队列的实现原理

如果队列是空的，消费者会一直等待，当生产者添加元素时，消费者是如何知道当前队列 有元素的呢？如果让你来设计阻塞队列你会如何设计，如何让生产者和消费者进行高效率的 通信呢？让我们先来看看JDK是如何实现的。

使用通知模式实现。所谓通知模式，就是当生产者往满的队列里添加元素时会阻塞住生 产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。通过查看JDK源码 发现ArrayBlockingQueue使用了Condition来实现，代码如下。

    private final Condition notFull;
    private final Condition notEmpty;
    public ArrayBlockingQueue(int capacity, boolean fair) {
// 省略其他代码
        notEmpty = lock.newCondition();
        notFull = lock.newCondition();
    }
    public void put(E e) throws InterruptedException {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == items.length)
                notFull.await();
            insert(e);
        } finally {
            lock.unlock();
        }
    }
    public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == 0)
                notEmpty.await();
            return extract();
        } finally {
            lock.unlock();
        }
    }
    private void insert(E x) {
        items[putIndex] = x;
        putIndex = inc(putIndex);
        ++count;
        notEmpty.signal();
    }

当往队列里插入一个元素时，如果队列不可用，那么阻塞生产者主要通过 LockSupport.park（this）来实现。

public final void await() throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        Node node = addConditionWaiter();
        int savedState = fullyRelease(node);
        int interruptMode = 0;
        while (!isOnSyncQueue(node)) {
            LockSupport.park(this);
            if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                break;
        }
        if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
            interruptMode = REINTERRUPT;
        if (node.nextWaiter != null) // clean up if cancelled
            unlinkCancelledWaiters();
        if (interruptMode != 0)
            reportInterruptAfterWait(interruptMode);
    }

继续进入源码，发现调用setBlocker先保存一下将要阻塞的线程，然后调用unsafe.park阻塞 当前线程。

public static void park(Object blocker) {
Thread t = Thread.currentThread();
setBlocker(t, blocker);
unsafe.park(false, 0L);
setBlocker(t, null);
}

unsafe.park是个native方法，代码如下。

public native void park(boolean isAbsolute, long time);

park这个方法会阻塞当前线程，只有以下4种情况中的一种发生时，该方法才会返回。

• 与park对应的unpark执行或已经执行时。“已经执行”是指unpark先执行，然后再执行park 的情况。
• 线程被中断时。
• 等待完time参数指定的毫秒数时。
• 异常现象发生时，这个异常现象没有任何原因。

继续看一下JVM是如何实现park方法：park在不同的操作系统中使用不同的方式实现，在 Linux下使用的是系统方法pthread_cond_wait实现。实现代码在JVM源码路径 src/os/linux/vm/os_linux.cpp里的os::PlatformEvent::park方法，代码如下。

    void os::PlatformEvent::park() {
        int v ;
        for (;;) {
            v = _Event ;
            if (Atomic::cmpxchg (v-1, &_Event, v) == v) break ;
        }
        guarantee (v >= 0, "invariant") ;
        if (v == 0) {
// Do this the hard way by blocking ...
            int status = pthread_mutex_lock(_mutex);
            assert_status(status == 0, status, "mutex_lock");
            guarantee (_nParked == 0, "invariant") ;
            ++ _nParked ;
            while (_Event < 0) {
                status = pthread_cond_wait(_cond, _mutex);
// for some reason, under 2.7 lwp_cond_wait() may return ETIME ...
// Treat this the same as if the wait was interrupted
                if (status == ETIME) { status = EINTR; }
                assert_status(status == 0 || status == EINTR, status, "cond_wait");
            }
            -- _nParked ;
// In theory we could move the ST of 0 into _Event past the unlock(),
// but then we'd need a MEMBAR after the ST.
            _Event = 0 ;
            status = pthread_mutex_unlock(_mutex);
            assert_status(status == 0, status, "mutex_unlock");
        }
        guarantee (_Event >= 0, "invariant") ;
    }
}

pthread_cond_wait是一个多线程的条件变量函数，cond是condition的缩写，字面意思可以 理解为线程在等待一个条件发生，这个条件是一个全局变量。这个方法接收两个参数：一个共 享变量_cond，一个互斥量_mutex。而unpark方法在Linux下是使用pthread_cond_signal实现的。 park方法在Windows下则是使用WaitForSingleObject实现的。想知道pthread_cond_wait是如何实 现的，可以参考glibc-2.5的nptl/sysdeps/pthread/pthread_cond_wait.c。

当线程被阻塞队列阻塞时，线程会进入WAITING（parking）状态。我们可以使用jstack dump 阻塞的生产者线程看到这点，如下。

"main" prio=5 tid=0x00007fc83c000000 nid=0x10164e000 waiting on condition [0x000000010164d000]
java.lang.Thread.State: WAITING (parking)
at sun.misc.Unsafe.park(Native Method)
- parking to wait for <0x0000000140559fe8> (a java.util.concurrent.locks.
AbstractQueuedSynchronizer$ConditionObject)
at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.
await(AbstractQueuedSynchronizer.java:2043)
at java.util.concurrent.ArrayBlockingQueue.put(ArrayBlockingQueue.java:324)
at blockingqueue.ArrayBlockingQueueTest.main(ArrayBlockingQueueTest.java

4、阻塞队列使用场景

4.1、⽣产者-消费者模型

public class Test {
    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);
    public static void main(String[] args) {
        Test test = new Test();
        Producer producer = test.new Producer();
        Consumer consumer = test.new Consumer();
        producer.start();
        consumer.start();
    }
    class Consumer extends Thread{
        @Override
        public void run() {
            consume();
        }
        private void consume() {
            while(true){
                try {
                    queue.take();
                    System.out.println("从队列取⾛⼀个元素，队列剩余"+queue.size()+"元素");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    class Producer extends Thread{
        @Override
        public void run() {
            produce();
        }
        private void produce() {
            while(true){
                try {
                    queue.put(1);
                    System.out.println("向队列取中插⼊⼀个元素，队列剩余空间："+queue.size());
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

输出片段

从队列取⾛⼀个元素，队列剩余0个元素
从队列取⾛⼀个元素，队列剩余0个元素
向队列取中插⼊⼀个元素，队列剩余空间：9
向队列取中插⼊⼀个元素，队列剩余空间：9
向队列取中插⼊⼀个元素，队列剩余空间：9
向队列取中插⼊⼀个元素，队列剩余空间：8
向队列取中插⼊⼀个元素，队列剩余空间：7
向队列取中插⼊⼀个元素，队列剩余空间：6
向队列取中插⼊⼀个元素，队列剩余空间：5
向队列取中插⼊⼀个元素，队列剩余空间：4
向队列取中插⼊⼀个元素，队列剩余空间：3
向队列取中插⼊⼀个元素，队列剩余空间：2
向队列取中插⼊⼀个元素，队列剩余空间：1
向队列取中插⼊⼀个元素，队列剩余空间：0
从队列取⾛⼀个元素，队列剩余1个元素
从队列取⾛⼀个元素，队列剩余9个元素

注意，这个例⼦中的输出结果看起来可能有问题，⽐如有⼏⾏在插⼊⼀个元素之 后，队列的剩余空间不变。这是由于System.out.println语句没有锁。考虑到这样 的情况：线程1在执⾏完put/take操作后⽴即失去CPU时间⽚，然后切换到线程2执 ⾏put/take操作，执⾏完毕后回到线程1的System.out.println语句并输出，发现这个 时候阻塞队列的size已经被线程2改变了，所以这个时候输出的size并不是当时线程 1执⾏完put/take操作之后阻塞队列的size，但可以确保的是size不会超过10个。实 际上使⽤阻塞队列是没有问题的。

4.2、线程池中使⽤阻塞队列

    public ThreadPoolExecutor(int corePoolSize,
                              int maximumPoolSize,
                              long keepAliveTime,
                              TimeUnit unit,
                              BlockingQueue<Runnable> workQueue) {
        this(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue,
                Executors.defaultThreadFactory(), defaultHandler);
    }

Java中的线程池就是使⽤阻塞队列实现的

小结

1.线程安全与线程不安全集合 集合类型中存在线程安全与线程不安全的两种,常见例如:

ArrayList ----- Vector

HashMap ---- HashTable

但是以上都是通过 synchronized 关键字实现,效率较低

2.Collections 构建的线程安全集合