Java的ConcurrentLinkedQueue
简介
实现一个线程安全的队列有两种实现方式一种是使用阻塞算法，另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现，而非阻塞的实现方式则可以使用循环CAS的方式来实现。
下面就来学习一下本文的主角ConcurrentLinkedQueue：
1）ConcurrentLinkedQueue的结构 2）offer方法原理 3）poll方法原理 4）HOPS设计
ConcurrentLinkedQueue的结构
首先看一下源码，从中你可以发现，它就是个队列的数据结构。
private static class Node<E> {
volatile E item;
volatile Node<E> next;
//省略了很多。。。
........
}
//头节点
private transient volatile Node<E> head;
//尾节点
private transient volatile Node<E> tail;
public ConcurrentLinkedQueue() {
//初始化时，头尾节点都指向同一个null节点。
head = tail = new Node<E>(null);
}Node节点主要包含了两个域：
一个是数据域item，另一个是next指针，用于指向下一个节点从而构成链式队列，并且都是用volatile进行修饰的，以保证内存可见性。而默认构造函数，head和tail指针会指向一个item域为null的节点。
offer方法原理
入队列就是将入队节点添加到队列的尾部。
public boolean offer(E e) {
checkNotNull(e);
// 新建一个node
final Node<E> newNode = new Node<E>(e);
// 不断重试（for只有初始化条件，没有判断条件），直到将node加入队列
// 初始化p、t都是指向tail
// 循环过程中一直让p指向最后一个节点。让t指向tail
for (Node<E> t = tail, p = t;;) {
// q一直指向p的下一个
Node<E> q = p.next;
if (q == null) {
// p is last node
// 如果q为null表示p是最后一个元素，尝试加入队列
// 如果失败，表示其他线程已经修改了p指向的节点
if (p.casNext(null, newNode)) {
// Successful CAS is the linearization point
// for e to become an element of this queue,
// and for newNode to become "live".
// node加入队列之后，tail距离最后一个节点已经相差大于一个了，需要更新tail
if (p != t) // hop two nodes at a time
// 这儿允许设置tail为最新节点的时候失败，因为添加node的时候是根据p.next是不是为null判断的，
casTail(t, newNode); // Failure is OK.
return true;
}
// Lost CAS race to another thread; re-read next
}
else if (p == q)
// 虽然q是p.next，但是因为是多线程，在offer的同时也在poll，如offer的时候正好p被poll了，那么在poll方法中的updateHead方法会将head指向当前的q，而把p.next指向自己，即：p.next == p
// 这个时候就会造成tail在head的前面，需要重新设置p
// 如果tail已经改变，将p指向tail，但这个时候tail依然可能在head前面
// 如果tail没有改变，直接将p指向head
// We have fallen off list. If tail is unchanged, it
// will also be off-list, in which case we need to
// jump to head, from which all live nodes are always
// reachable. Else the new tail is a better bet.
p = (t != (t = tail)) ? t : head;
else
// Check for tail updates after two hops.
// tail已经不是最后一个节点，将p指向最后一个节点
p = (p != t && t != (t = tail)) ? t : q;
}
}入队列就是将入队节点添加到队列的尾部。为了方便理解入队时队列的变化，以及head节点和tair节点的变化，每添加一个节点做了一个队列的快照图。
上图的步骤解析如下：
第一步添加元素1。队列更新head节点指向元素1，head的next指向是null。tail节点指向还是原来的null。第二步添加元素2。队列更新head节点指向元素1，head的next节点指向是元素2，而此时tail节点指向元素2，tail的next指向null。第三步添加元素3，添加完后tail节点指向元素2，而tail的next节点指向元素3。第四步添加元素4，添加完后tail节点指向元素4，然后将tail的next指向null。
可能你还是不相信，那么我们debug看看是否真的是如此的
那么它是如何保证多线程下安全的呢？
从源代码角度来看整个入队过程主要做二件事情：
第一是定位出尾节点。
Node<E> q = p.next;
if (q == null) {
................//省略很多代码
}else if (p == q)
p = (t != (t = tail)) ? t : head;
else
p = (p != t && t != (t = tail)) ? t : q;虽然q是p.next，但是因为是多线程，在offer的同时也在poll，如offer的时候正好p被poll了，那么在poll方法中的updateHead方法会将head指向当前的q，而把p.next指向自己，即：p.next == p这个时候就会造成tail在head的前面，需要重新设置p如果tail已经改变，将p指向tail，但这个时候tail依然可能在head前面 如果tail没有改变，直接将p指向head
第二是使用CAS算法能将入队节点设置成尾节点的next节点，如不成功则重试。
p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next节点，p如果是null表示p是当前队列的尾节点，如果不为null表示有其他线程更新了尾节点，则需要重新获取当前队列的尾节点。
大致示意图如下：
poll()方法原理
出队列的就是从队列里返回一个节点元素，并清空该节点对元素的引用。下面让我们通过每个节点出队的快照来观察下head节点的变化。
从上图可知，并不是每次出队时都更新head节点，当head节点里有元素时，直接弹出head节点里的元素，而不会更新head节点。只有当head节点里没有元素时，出队操作才会更新head节点。这种做法也是通过hops来减少使用CAS更新head节点的消耗，从而提高出队效率。让我们再通过源码来深入分析下出队过程。
public E poll() {
// 如果出现p被删除的情况需要从head重新开始
restartFromHead:
for (;;) {
for (Node<E> h = head, p = h, q;;) {
E item = p.item;
if (item != null && p.casItem(item, null)) {
// Successful CAS is the linearization point
// for item to be removed from this queue.
if (p != h) // hop two nodes at a time
updateHead(h, ((q = p.next) != null) ? q : p);
return item;
}
else if ((q = p.next) == null) {
// 队列为空
updateHead(h, p);
return null;
}
else if (p == q)
// 当一个线程在poll的时候，另一个线程已经把当前的p从队列中删除——将p.next = p，p已经被移除不能继续，需要重新开始
continue restartFromHead;
else
p = q;
}
}
}
final void updateHead(Node<E> h, Node<E> p) {
if (h != p && casHead(h, p))
h.lazySetNext(h);
}首先获取头节点的元素，然后判断头节点元素是否为空，如果为空，表示另外一个线程已经进行了一次出队操作将该节点的元素取走，如果不为空，则使用CAS的方式将头节点的引用设置成null，如果CAS成功，则直接返回头节点的元素，如果不成功，表示另外一个线程已经进行了一次出队操作更新了head节点，导致元素发生了变化，需要重新获取头节点。
HOPS的设计
通过上面对offer和poll方法的分析，我们发现tail和head是延迟更新的，两者更新触发时机为：
tail更新触发时机：当tail指向的节点的下一个节点不为null的时候，会执行定位队列真正的队尾节点的操作，找到队尾节点后完成插入之后才会通过casTail进行tail更新；当tail指向的节点的下一个节点为null的时候，只插入节点不更新tail。
head更新触发时机：当head指向的节点的item域为null的时候，会执行定位队列真正的队头节点的操作，找到队头节点后完成删除之后才会通过updateHead进行head更新；当head指向的节点的item域不为null的时候，只删除节点不更新head。
总结
站在巨人的肩膀上，才能看得更远。比如下面的两篇优秀文章可以阅读。
参考文章
http://ifeve.com/concurrentlinkedqueue/ https://juejin.im/post/5aeeae756fb9a07ab11112af