ConcurrentLinkedQueue的源码解析（基于JDK1.8）

ConcurrentLinkedQueue的源码解析（基于JDK1.8）

ConcurrentLinkedQueue是Java集合框架中的一种线程安全的队列，它是通过CAS（Compare and Swap）算法实现的并发队列。在并发场景下，ConcurrentLinkedQueue能够保证队列的线程安全性，同时性能也很不错。

数据结构

ConcurrentLinkedQueue是基于链表实现的队列，内部维护一个head节点和tail节点，head和tail都是指向链表中的节点。

入队操作

ConcurrentLinkedQueue的入队操作通过CAS算法实现，它的核心代码如下：

public boolean offer(E e) {checkNotNull(e);final Node<E> newNode = new Node<E>(e);for (Node<E> t = tail, p = t;;) {Node<E> q = p.next;if (q == null) {// p is last nodeif (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".if (p != t) // hop two nodes at a timecasTail(t, newNode);  // Failure is OK.return true;}// Lost CAS race to another thread; re-read next}else if (p == q)// 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.p = (p != t && t != (t = tail)) ? t : q;}
}

它的流程如下：

1. 首先，创建一个新节点newNode。
2. 获取tail节点和tail节点的下一个节点p。
3. 如果p为空，则说明当前节点p是队列中的最后一个节点，这时候尝试通过CAS将新节点newNode插入到链表中。
4. 如果CAS操作成功，则表示插入成功，并且将tail指针指向新的节点newNode。
5. 如果CAS操作失败，则说明有其他线程已经修改了tail指针，需要重新获取tail指针。
6. 如果p不为空，则需要判断p和tail是否指向同一个节点，如果是，则说明tail指针已经落后了，需要重新获取tail指针。
7. 如果p和tail不是同一个节点，则需要将p指向p的下一个节点。
8. 重复上述过程，直到插入成功为止。

出队操作

ConcurrentLinkedQueue的出队操作也是通过CAS算法实现，它的核心代码如下：

public E poll() {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 timeupdateHead(h, ((q = p.next) != null) ? q : p);return item;}else if ((q = p.next) == null) {updateHead(h, p);return null;}else if (p == q)continue restartFromHead;elsep = q;}}
}

它的流程如下：

1. 首先，获取head节点和head节点的下一个节点p。
2. 如果p为空，则说明队列为空，直接返回null。
3. 如果p不为空，则尝试通过CAS将p节点的元素item设置为null。
4. 如果CAS操作成功，则表示当前节点p被成功出队，并且返回出队的元素item。
5. 如果CAS操作失败，则说明有其他线程已经修改了当前节点p的元素item，需要重新获取head节点。
6. 如果p的下一个节点q为空，则需要更新head节点为p，并返回null。
7. 如果p和p的下一个节点q是同一个节点，则说明head节点已经落后了，需要重新获取head节点。
8. 如果p和p的下一个节点q不是同一个节点，则将p指向q。
9. 重复上述过程，直到出队成功为止。

总结

ConcurrentLinkedQueue是一种高效的并发队列，它通过CAS算法实现了线程安全的入队和出队操作。在并发场景下，ConcurrentLinkedQueue能够保证队列的线程安全性，同时性能也很不错。因此，在Java并发编程中，ConcurrentLinkedQueue是一种常用的数据结构。