Java 集合 ConcurrentLinkedQueue

简介

ConcurrentLinkedQueue是一个基于链表实现的无界线程安全非阻塞队列，采用先进先出规则，新入队的节点在队列的尾部，获取元素时从队列头部返回。这个类的最显著的特点是，head 和 tail 都不一定指向真实的头结点和尾结点。

offer(E e)方法每两次操作入队才会推进一次tail节点，目的是为了减少CAS的调用次数，这是导致tail不一定指向真实尾节点的原因。这直接导致 head 不一定指向真实头结点，tail 也不一定指向真实尾结点，这样设计的目的是为了减少CAS的次数。

poll()方法也是每两次操作出队才会更新一次head节点，获取头部元素时，会把头部元素的item置为null，成功之后会再把头节点指向自己（可以叫冲洗 / 自引用）以达到回收的目的。多线程情况下，另一个线程如果发现头节点被冲洗时，会重新获取头节点然后再次尝试。

使用size()方法获取队列元素总数时效率会比较低，因为size()方法内部是通过遍历链表实现的。只需要判断链表是否为空时，用isEmpty()方法效率更高，因为它只判断头节点是否为null。

代码细节

offer(E e)

代码注释

    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;
			// 下一个节点为空 说明当前节点是尾结点 CAS设置新节点
            if (q == null) {
                // p is last node
                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".
					// 连续插入2个节点 由于插入第一个元素不会更新tail 
					// 因此插入第二个元素的时候会走到else的逻辑 
					// 导致下一轮循环中 p!=t 这时候就会更新tail 
					// 也就是说tail不一定指向真实尾结点
                    if (p != t) // hop two nodes at a time
						// 更新失败了也没关系 因为失败了表示有其他线程成功更新了tail节点
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
			// 由于poll()会把头结点设置为自引用
			// 当出现并发入队出队时就可能出现 p == q 的情况
            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.
				// 走到这里说明已经从链表上被摘下来了
				// 所以必须回到主链表才能继续执行
				// tail变了优先取tail 否则就取head
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
				// 这里的逻辑和上一个分支类似
				// 也是tail变了优先取tail 否则就取q
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

poll()

    public E poll() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                E item = p.item;

				// 若head指向的就是真实头结点 直接出队
                if (item != null && p.casItem(item, null)) {
                    // Successful CAS is the linearization point
                    // for item to be removed from this queue.
					// 插入一个节点后立刻删除节点
					// 此时head指向的不是真实头结点
					// 因此会走到else逻辑取下一个节点
					// 此时就会出现 p != h 的情况
					// 这时候就需要更新head
                    if (p != h) // hop two nodes at a time
                        updateHead(h, ((q = p.next) != null) ? q : p);
                    return item;
                }
				// 若下一个节点也是null 说明队列空了
				// 设置自引用 然后直接返回null即可
                else if ((q = p.next) == null) {
                    updateHead(h, p);
                    return null;
                }
				// 发现自引用 回到外部循环找最新head重试
                else if (p == q)
                    continue restartFromHead;
				// 若当前节点为空节点 不是自引用节点
				// 并且下一个节点不为null 直接让p指向下一个节点
				// 进入下一轮循环处理
                else
                    p = q;
            }
        }
    }