15-JUC 集合包中 List 和 Set 实现类

对于数据集合的存储使用，基于 Java 类集框架（List、Set、Map、Queue），这些类集的子类都是具有同步和异步的差别。但是对于多线程高并发而言，并不一定适合使用。JUC 中提供了并发处理集合的支持类。

JUC 集合包中的 List 和 Set 实现类

JUC 集合包中的 List 和 Set 实现类包含 CopyOnWriteArrayList, CopyOnWriteArraySet 和 ConcurrentSkipListSet。

CopyOnWriteArrayList

是一个线程安全的有序的可重复的动态数组，相当于线程安全的 ArrayList。和 ArrayList 一样，它是个可变数组；但是和 ArrayList 不同，它具有以下特性：

1、它最适合于具有以下特征的应用程序：List 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突；

2、它是线程安全的；

3、因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大；

4、迭代器支持 hasNext()，next()等不可变操作，但不支持可变 remove()等操作；

5、使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。

1、内部结构

public class CopyOnWriteArrayList<E>extends Objectimplements List<E>, RandomAccess, Cloneable, Serializable{
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;}

说明

1. CopyOnWriteArrayList 实现了 List 接口，因此它是一个队列。

2. CopyOnWriteArrayList 包含了成员 lock。每一个 CopyOnWriteArrayList 都和一个互斥锁 lock 绑定，通过 lock，实现了对 CopyOnWriteArrayList 的互斥访问。

3. CopyOnWriteArrayList 包含了成员 array 数组，这说明 CopyOnWriteArrayList 本质上通过数组实现的。

由于 CopyOnWriteArrayList 是 List 的子类，其方法继承自 List，故在此不赘述了。

2、常用方法

public void add(int index,E element)：制定位置添加元素

public boolean addIfAbsent​(E e)：添加未存在新元素

public int addAllAbsent​(Collection c)：添加未存在集合

public E remove​(int index)：删除指定位置元素

public E set​(int index,E element)：修改制定位置元素

public E get​(int index)：获取指定索引的数据

但在此需要关注 add()添加方法，设计到如何实现动态数组和线程安全。

3、add()方法

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;        setArray(newElements);        return true;    } finally {        lock.unlock();    }}

下面从“动态数组”和“线程安全”两个方面进一步对 CopyOnWriteArrayList 的原理进行说明。

1）“动态数组”机制

CopyOnWriteArrayList 内部有个“volatile 数组”(array)来保持数据。

通过 volatile 修饰数组，一个线程对于该数组进行读取操作，能够看到其他线程对于此数组最新的修改，充分体现了可见性。

在“添加/修改/删除”数据时，都会新建一个数组，并将更新后的数据拷贝到新建的数组中，最后再将该数组赋值给“volatile 数组”。这就是它叫做 CopyOnWriteArrayList 的原因！CopyOnWriteArrayList 就是通过这种方式实现的动态数组。

不过正由于它在“添加/修改/删除”数据时，都会新建数组，所以涉及到修改数据的操作，CopyOnWriteArrayList 效率很低；但是单单只是进行遍历查找的话，效率比较高。

2）“线程安全”机制

CopyOnWriteArrayList 通过互斥锁来保护数据。在“添加/修改/删除”数据时，会先“获取互斥锁”，再修改完毕之后，先将数据更新到“volatile 数组”中，然后再“释放互斥锁”；这样，就达到了保护数据的目的。

CopyOnWriteArraySet

它是线程安全的有序的不可重复的动态数组，可以理解成线程安全的 HashSet。有意思的是，CopyOnWriteArraySet 和 HashSet 虽然都继承于共同的父类 AbstractSet；但是，HashSet 是通过“散列哈希表(HashMap)”实现的，而 CopyOnWriteArraySet 则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。

和 CopyOnWriteArrayList 类似，CopyOnWriteArraySet 具有以下特性：

1、它最适合于具有以下特征的应用程序：Set 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突；

2、它是线程安全的；

3、因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大；

4、迭代器支持 hasNext(), next()等不可变操作，但不支持可变 remove()等操作；

5、使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。

1、内部结构

public class CopyOnWriteArraySet<E>extends AbstractSet<E>implements Serializable{
	private final CopyOnWriteArrayList<E> al;}

说明

1、CopyOnWriteArraySet 继承于 AbstractSet，这就意味着它是一个集合；

2、CopyOnWriteArraySet 包含 CopyOnWriteArrayList 对象，它是通过 CopyOnWriteArrayList 实现的。而 CopyOnWriteArrayList 本质是个动态数组队列，所以 CopyOnWriteArraySet 相当于通过动态数组实现的“集合”。

3、至于 CopyOnWriteArraySet 的“动态数组”和“线程安全”机制，依赖于 CopyOnWriteArrayList 实现。

CopyOnWriteArraySet 主要是通过 CopyOnWriteArrayList 实现，故不在此赘述使用方法了。

2、常用方法

public boolean add​(E e)：添加元素

public boolean addAll​(Collection c)：添加集合

public Iterator iterator​()：遍历集合

3、add()方法

public boolean add(E e) {

return al.addIfAbsent(e);

}

CopyOnWriteArrayList 中允许有重复的元素。但是，CopyOnWriteArraySet 是不能有重复元素的集合。因此，CopyOnWriteArrayList 额外提供了 addIfAbsent()和 addAllAbsent()这两个添加元素的 API，通过这些 API 来添加元素时，只有当元素不存在时才执行添加操作。

16-JUC 集合包中 Map 实现类

JUC 集合包中 Map 的实现类

JUC 集合包中 Map 的实现类包括：ConcurrentHashMap 和 ConcurrentSkipListMap。

ConcurrentHashMap

ConcurrentHashMap 是线程安全的无序的哈希表。

HashMap, Hashtable, ConcurrentHashMap 之间的关联如下：

HashMap 是非线程安全的哈希表，常用于单线程程序中。

Hashtable 是线程安全的哈希表，它是通过 synchronized 来保证线程安全的，即，多线程通过同一个“对象的同步锁”来实现并发控制。Hashtable 在线程竞争激烈时，效率比较低(此时建议使用 ConcurrentHashMap)。因为当一个线程访问 Hashtable 的同步方法时，其它线程就访问 Hashtable 的同步方法时，可能会进入阻塞状态。

ConcurrentHashMap 是线程安全的哈希表，它是通过“同步锁”来保证线程安全的。数据结构上与 HashMap 相同，但是，在进行同一个节点下的链表操作时，使用同步锁进行操作，保证了线程安全。这与 jdk1.7 锁分段的方式完全不同。同样使用了同步锁，Hashtable 锁的是方法，而 ConcurrentHashMap 锁的代码块。

1、内部结构

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {
	private transient volatile int sizeCtl;
	transient volatile Node<K, V>[] table;
	static class Node<K, V> implements Map.Entry<K, V> {		final int hash;		final K key;		volatile V val;		volatile Node<K, V> next;		private static final sun.misc.Unsafe UNSAFE;	}
}

(01)ConcurrentHashMap 继承于 AbstractMap 抽象类。

(05)对于多线程访问对一个“哈希表对象”竞争资源，Hashtable 是通过一把锁来控制并发；而 ConcurrentHashMap 则是将同步锁更加细化，只是针对数组中的同一链表下的操作使用，当然肯定符合高并发场景。

2、构造方法

public ConcurrentHashMap​(int initialCapacity,float loadFactor,int concurrencyLevel)

参数说明

initialCapacity：哈希表的初始容量

loadFactor：加载因子，也叫表密度，用于建立初始表大小

concurrencyLevel：并发更新线程数

3、常用方法

public V put​(K key,V value)：保存键值对

public V putIfAbsent​(K key,V value)：保存不存在的键值对

public boolean remove​(Object key,Object value)：删除已存在的键值对

public V get​(Object key)：获取指定 key 的 value 指

public V getOrDefault​(Object key,V defaultValue)：获取指定 key 的 value 值，并设置未获取到 value 值时的默认值

4、get()方法

思路解析：

1）根据 spread(int h)方法获取 key 在对象数组 table 中的索引位置

2）其中包含 tabAt(Node[] tab, int i)方法获取对应索引下的单向链表头节点

3）若该节点不存在，则返回空；若节点存在，则进行 key 比较，相同，则返回 value 值，不同，则遍历链表，进行 key 比较，找到相同的，则返回 value，若一直匹配不到，则返回空

5、put()方法

思路解析：

这里需要说明的是，jdk1.8 实现的方式已经与 1.7 完全不同，1.7 是使用锁分段的方式实现，1.8 则是使用对象数组，对于数据的安全，使用了 synchronized 同步锁，而仍然保留 1.7 的 segment，只不过对于该类的使用方式，用于序列化和数据流。

1）根据 spread(int h)方法获取 key 在对象数组 table 中的索引位置

2）进入对象数组循环

3）判断数组是否为空，若为空，则进行表的初始化

4）通过 tabAt(Node[] tab, int i)，查询出具体索引下的节点

5）若节点为空，则直接添加，若节点不为空，则进行同步锁控制

6）此时，进行节点 key 比较，若是相同，则进行 value 替换，若 key 不同，则将新的 key-value 节点作为下一个节点存储

7）最后，通过 addCount(long x, int check)方法进行扩容判断处理

ConcurrentSkipListMap

ConcurrentSkipListMap 是线程安全的有序的哈希表，适用于高并发的场景。

ConcurrentSkipListMap 和 TreeMap，它们虽然都是有序的哈希表。但是，第一，它们的线程安全机制不同，TreeMap 是非线程安全的，而 ConcurrentSkipListMap 是线程安全的。第二，ConcurrentSkipListMap 是通过跳表实现的，而 TreeMap 是通过红黑树实现的。

关于跳表(Skip List)，它是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

1、内部结构

public class ConcurrentSkipListMap<K,V>extends AbstractMap<K,V>implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable{
private transient volatile HeadIndex<K,V> head;
static final class HeadIndex<K,V> extends Index<K,V> {    final int level;    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {        super(node, down, right);        this.level = level;    }}
static class Index<K,V> {    final Node<K,V> node;    final Index<K,V> down;    volatile Index<K,V> right;}
static final class Node<K,V> {    final K key;    volatile Object value;    volatile Node<K,V> next;}}

说明

先以数据“7,14,21,32,37,71,85”序列为例，来对跳表进行简单说明。

跳表分为许多层(level)，每一层都可以看作是数据的索引，这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的，上一层数据是下一层数据的子集，并且第一层(level 1)包含了全部的数据；层次越高，跳跃性越大，包含的数据越少。

跳表包含一个表头，它查找数据时，是从上往下，从左往右进行查找。现在“需要找出值为 32 的节点”为例，来对比说明跳表和普遍的链表。

情况 1：链表中查找“32”节点

需要 4 步(红色部分表示路径)。

情况 2：跳表中查找“32”节点

忽略索引垂直线路上路径的情况下，只需要 2 步(红色部分表示路径)。

下面说说 Java 中 ConcurrentSkipListMap 的数据结构。

(01)ConcurrentSkipListMap 继承于 AbstractMap 类，也就意味着它是一个哈希表。

(02)Index 是 ConcurrentSkipListMap 的内部类，它与“跳表中的索引相对应”。HeadIndex 继承于 Index，ConcurrentSkipListMap 中含有一个 HeadIndex 的对象 head，head 是“跳表的表头”。

(03)Index 是跳表中的索引，它包含“右索引的指针(right)”，“下索引的指针(down)”和“哈希表节点 node”。node 是 Node 的对象，Node 也是 ConcurrentSkipListMap 中的内部类。

(04)实际上，存储每个数据的节点只有一个，而整个跳表结构只不过是不断创建索引对象，然后，将节点进行引用传递。

2、构造方法中的 initialize()方法

private void initialize() {    keySet = null;    entrySet = null;    values = null;    descendingMap = null;    head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),                              null, null, 1);}

ConcurrentSkipListMap 常用方法如同 Map 定义一样使用即可，但是在此特殊讲解特定方法。

3、get()方法

public V get(Object key) {
 return doGet(key);
}
//只展示核心环节
private V doGet(Object key) {    Comparator<? super K> cmp = comparator;    outer: for (;;) {        for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {            Object v;             int c;            if ((v = n.value) == null) {    // n is deleted            	n.helpDelete(b, f);            	break;            }            if ((c = cpr(cmp, key, n.key)) == 0) {                @SuppressWarnings("unchecked") V vv = (V)v;                return vv;            }        }    }    return null;}

4、put()方法

public V put​(K key,V value){if (value == null)    throw new NullPointerException();return doPut(key, value, false);}
// 展示核心环节private V doPut(K kkey, V value, boolean onlyIfAbsent) {    Comparable<? super K> key = comparable(kkey);    for (;;) {        // 找到key的前继节点        Node<K,V> b = findPredecessor(key);        // 设置n为key的后继节点        Node<K,V> n = b.next;        for (;;) {                        // 新建节点(对应是“要被插入的键值对”)            Node<K,V> z = new Node<K,V>(kkey, value, n);            // 设置“b的后继节点”为z            b.casNext(n, z);
            // 随机获取一个level            // 然后在“第1层”到“第level层”的链表中都插入新建节点            int level = randomLevel();            if (level > 0)                insertIndex(z, level);            return null;        }    }}

说明

doPut() 的作用就是将键值对添加到“跳表”中。

第 1 步：找到“插入位置”。

找到“key 的前继节点(b)”和“key 的后继节点(n)”；key 是要插入节点的键。

第 2 步：新建并插入节点。

新建节点 z(key 对应的节点)，并将新节点 z 插入到“跳表”中(设置“b 的后继节点为 z”，“z 的后继节点为 n”)。

第 3 步：更新跳表。

随机获取一个 level，然后在“跳表”的第 1 层～第 level 层之间，每一层都插入节点 z；在第 level 层之上就不再插入节点了。若 level 数值大于“跳表的层次”，则新建一层。

remove()方法主干部分

public V remove(Object key) {    return doRemove(key, null);}
final V doRemove(Object okey, Object value) {    Comparable<? super K> key = comparable(okey);    for (;;) {        // 找到“key的前继节点”        Node<K,V> b = findPredecessor(key);        // 设置n为“b的后继节点”(即若key存在于“跳表中”，n就是key对应的节点)        Node<K,V> n = b.next;        for (;;) {            // f是“当前节点n的后继节点”            Node<K,V> f = n.next;
            // 设置“当前节点n”的值为null            n.casValue(v, null);
            // 设置“b的后继节点”为f            b.casNext(n, f);            // 清除“跳表”中每一层的key节点            findPredecessor(key);            // 如果“表头的右索引为空”，则将“跳表的层次”-1。            if (head.right == null)                tryReduceLevel();            return (V)v;        }    }}

说明：

doRemove()的作用是删除跳表中的节点。

第 1 步：找到“被删除节点的位置”。

找到“key 的前继节点(b)”，“key 所对应的节点(n)”，“n 的后继节点 f”；key 是要删除节点的键。

第 2 步：删除节点。

将“key 所对应的节点 n”从跳表中移除，同时将“b 的后继节点”设为“f”。

第 3 步：更新跳表。

遍历跳表，删除每一层的“key 节点”(如果存在的话)。如果删除“key 节点”之后，跳表的层次需要-1；则执行相应的操作。

ConcurrentSkipListSet

ConcurrentSkipListSet 是线程安全的有序的集合，适用于高并发的场景。

ConcurrentSkipListSet 和 TreeSet，它们虽然都是有序的集合。但是，第一，它们的线程安全机制不同，TreeSet 是非线程安全的，而 ConcurrentSkipListSet 是线程安全的。第二，ConcurrentSkipListSet 是通过 ConcurrentSkipListMap 实现的，而 TreeSet 是通过 TreeMap 实现的。

1、内部结构

public class ConcurrentSkipListSet<E>extends AbstractSet<E>implements NavigableSet<E>, Cloneable, Serializable{
private final ConcurrentNavigableMap<E,Object> m;
}

说明

(01) ConcurrentSkipListSet 继承于 AbstractSet。因此，它本质上是一个集合。

(02) ConcurrentSkipListSet 实现了 NavigableSet 接口。因此，ConcurrentSkipListSet 是一个有序的集合。

(03) ConcurrentSkipListSet 是通过 ConcurrentSkipListMap 实现的。它包含一个 ConcurrentNavigableMap 对象 m，而 m 对象实际上是 ConcurrentNavigableMap 的实现类 ConcurrentSkipListMap 的实例。ConcurrentSkipListMap 中的元素是 key-value 键值对；而 ConcurrentSkipListSet 是集合，它只用到了 ConcurrentSkipListMap 中的 key。

2、常用方法

public E first​()：获取第一个元素

public E last​()：获取最后一个元素

3、add()方法

public boolean add(E e) {

return m.putIfAbsent(e, Boolean.TRUE) == null;

}

17-JUC 集合包中 Queue 实现类

JUC 集合包中 Queue 的实现类

JUC 集合包中 Queue 的实现类包括: ArrayBlockingQueue, LinkedBlockingQueue, LinkedBlockingDeque, ConcurrentLinkedQueue 和 ConcurrentLinkedDeque。

（2）LinkedBlockingQueue 是单向链表实现的(指定大小)阻塞队列，该队列按 FIFO（先进先出）排序元素；

（3）LinkedBlockingDeque 是双向链表实现的(指定大小)双向并发阻塞队列，该阻塞队列同时支持 FIFO 和 FILO 两种操作方式；

（4）ConcurrentLinkedQueue 是单向链表实现的无界队列，该队列按 FIFO（先进先出）排序元素；

（5）ConcurrentLinkedDeque 是双向链表实现的无界队列，该队列同时支持 FIFO 和 FILO 两种操作方式。

ArrayBlockingQueue

ArrayBlockingQueue 是数组实现的线程安全的有界的阻塞队列。按照 FIFO（先进先出）原则对元素进行排序，元素都是从尾部插入到队列，从头部开始返回。

线程安全是指，ArrayBlockingQueue 内部通过“互斥锁”保护竞争资源，实现了多线程对竞争资源的互斥访问。而有界，则是指 ArrayBlockingQueue 对应的数组是有界限的。 阻塞队列，是指多线程访问竞争资源时，当竞争资源已被某线程获取时，其它要获取该资源的线程需要阻塞等待。

1、内部结构

public class ArrayBlockingQueue<E>extends AbstractQueue<E>implements BlockingQueue<E>, Serializable{final Object[] items;
final ReentrantLock lock;
private final Condition notEmpty;
private final Condition notFull;
int takeIndex;
int putIndex;
int count;}

说明

ArrayBlockingQueue 与 Condition 是组合关系，通过 Condition 可以实现对 ArrayBlockingQueue 的更精确的访问。

(01)若某线程(线程 A)要取数据时，数组正好为空，则该线程会执行 notEmpty.await()进行等待；当其它某个线程(线程 B)向数组中插入了数据之后，会调用 notEmpty.signal()唤醒“notEmpty 上的等待线程”。此时，线程 A 会被唤醒从而得以继续运行；

(02)若某线程(线程 H)要插入数据时，数组已满，则该线程会它执行 notFull.await()进行等待；当其它某个线程(线程 I)取出数据之后，会调用 notFull.signal()唤醒“notFull 上的等待线程”。此时，线程 H 就会被唤醒从而得以继续运行。

2、构造方法

public ArrayBlockingQueue​(int capacity,boolean fair,Collection c)：

创建指定容量和是否公平的阻塞队列

3、核心方法

public boolean add​(E e)：添加元素

public void put​(E e)throws InterruptedException：添加元素

public E poll​()：从数组头部取出元素

public void put​(E e)throws InterruptedException：从数组尾部放入元素

public E take​()throws InterruptedException：取出元素

public Iterator iterator​()：遍历元素

LinkedBlockingQueue

LinkedBlockingQueue 是一个单向链表实现的阻塞队列。该队列按 FIFO（先进先出）排序元素，新元素插入到队列的尾部，并且队列获取操作会获得位于队列头部的元素。链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。

此外，LinkedBlockingQueue 还是可选容量的(防止过度膨胀)，即可以指定队列的容量。如果不指定，默认容量大小等于 Integer.MAX_VALUE。

1、内部结构

public class LinkedBlockingQueue<E>extends AbstractQueue<E>implements BlockingQueue<E>, Serializable{
private final int capacity;
private final AtomicInteger count = new AtomicInteger();
transient Node<E> head;
private transient Node<E> last;
private final ReentrantLock takeLock = new ReentrantLock();
private final Condition notEmpty = takeLock.newCondition();
private final ReentrantLock putLock = new ReentrantLock();
private final Condition notFull = putLock.newCondition();
static class Node<E> {    E item;
    Node<E> next;
    Node(E x) { item = x; }}}

说明

LinkedBlockingQueue 是通过单链表实现的。

(01)head 是链表的表头。取出数据时，都是从表头 head 处取出。

(02)last 是链表的表尾。新增数据时，都是从表尾 last 处插入。

(03)count 是链表的实际大小，即当前链表中包含的节点个数。

(04)capacity 是列表的容量，它是在创建链表时指定的。

(05)putLock 是插入锁，takeLock 是取出锁；notEmpty 是“非空条件”，notFull 是“未满条件”。

通过它们对链表进行并发控制。LinkedBlockingQueue 在实现“多线程对竞争资源的互斥访问”时，对于“插入”和“取出(删除)”操作分别使用了不同的锁。对于插入操作，通过“插入锁 putLock”进行同步；对于取出操作，通过“取出锁 takeLock”进行同步。此外，插入锁 putLock 和“非满条件 notFull”相关联，取出锁 takeLock 和“非空条件 notEmpty”相关联。通过 notFull 和 notEmpty 更细腻的控制锁。

2、常用方法

public void put​(E e)throws InterruptedException：从链表尾部放入元素

public E poll​()：从链表头部取出元素

LinkedBlockingDeque

LinkedBlockingDeque 是双向链表实现的双向并发阻塞队列。该阻塞队列同时支持 FIFO 和 FILO 两种操作方式，即可以从队列的头和尾同时操作(插入/删除)；并且，该阻塞队列是支持线程安全。

此外，LinkedBlockingDeque 还是可选容量的(防止过度膨胀)，即可以指定队列的容量。如果不指定，默认容量大小等于 Integer.MAX_VALUE。

内部结构

public class LinkedBlockingDeque<E>extends AbstractQueue<E>implements BlockingDeque<E>, java.io.Serializable {transient Node<E> first;
transient Node<E> last;
private transient int count;
private final int capacity;
final ReentrantLock lock = new ReentrantLock();
private final Condition notEmpty = lock.newCondition();
private final Condition notFull = lock.newCondition();
static final class Node<E> {    E item;
    Node<E> prev;
    Node<E> next;}}

说明：

LinkedBlockingDeque 是通过双向链表实现的。

1、first 是双向链表的表头。

2、last 是双向链表的表尾。

3、count 是 LinkedBlockingDeque 的实际大小，即双向链表中当前节点个数。

4、capacity 是 LinkedBlockingDeque 的容量，它是在创建 LinkedBlockingDeque 时指定的。

5、lock 是控制对 LinkedBlockingDeque 的互斥锁，当多个线程竞争同时访问 LinkedBlockingDeque 时，某线程获取到了互斥锁 lock，其它线程则需要阻塞等待，直到该线程释放 lock，其它线程才有机会获取 lock 从而获取 cpu 执行权。

6、notEmpty 和 notFull 分别是“非空条件”和“未满条件”。通过它们能够更加细腻进行并发控制。

ConcurrentLinkedQueue

ConcurrentLinkedQueue 是线程安全的队列，它适用于“高并发”的场景。它是一个基于链接节点的无界线程安全队列，按照 FIFO（先进先出）原则对元素进行排序。队列元素中不可以放置 null 元素（内部实现的特殊节点除外）。

内部结构

public class ConcurrentLinkedQueue<E>extends AbstractQueue<E>implements Queue<E>, Serializable{
private static final sun.misc.Unsafe UNSAFE;
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
private static class Node<E> {    volatile E item;    volatile Node<E> next;}}

说明

1. ConcurrentLinkedQueue 继承于 AbstractQueue。

2. ConcurrentLinkedQueue 内部是通过链表来实现的。它同时包含链表的头节点 head 和尾节点 tail。ConcurrentLinkedQueue 按照 FIFO（先进先出）原则对元素进行排序。元素都是从尾部插入到链表，从头部开始返回。

3. ConcurrentLinkedQueue 的链表 Node 中的 next 的类型是 volatile，而且链表数据 item 的类型也是 volatile。关于 volatile，我们知道它的语义包含：“即对一个 volatile 变量的读，总是能看到（任意线程）对这个 volatile 变量最后的写入”。ConcurrentLinkedQueue 就是通过 volatile 来实现多线程对竞争资源的互斥访问的。