ConcurrentLinkedQueue解析

概述

        ConcurrentLinkedQueue实际对应的是LinkedList,是一个线程安全的无界队列，但LinkedList是一个双向链表，而ConcurrentLinkedQueue是单向链表。ConcurrentLinkedQueue线程安全在于设置head、tail以及next指针时都用的cas操作，而且node里的item和next变量都是用volatile修饰，保证了多线程下变量的可见性。而ConcurrentLinkedQueue的所有读操作都是无锁的，所以可能读会存在不一致性

add（"张三"）

无参构造器

publicConcurrentLinkedQueue(){
head = tail =new Node<E>(null);
}

初始化了一个node节点，head和tail指针都指向这个node，item和next都是null

for (Node t = tail, p = t;;) {

这个for循环是个死循环，增加了两个指针p，t。

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".
if(p != t)// hop two nodes at a time
casTail(t, newNode);// Failure is OK.
returntrue;
}
// Lost CAS race to another thread; re-read next
}
 

此时q指向的是null，所以会使用cas把newNode挂到p的next，此时p==t,所以casTail(t, newNode);不会执行，然后跳出,此时链表如下：

add("李四")

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".
if(p != t)// hop two nodes at a time
casTail(t, newNode);// Failure is OK.
returntrue;
}
// Lost CAS race to another thread; re-read next
}
 

此时进入for循环的时候如上图，q是指向了张三node，就不会进入q==null这个if，else if (p == q)这个也是不成立的，也就会进入else这个分支，

p = (p != t && t != (t = tail)) ? t : q;

这里实际就是移动p指针，意思就是此时如果p不是最后一个元素则把p指针指向tail，否则指向q，也就是指向p.next元素。

然后进入下一个for循环，指针如下图：

此时q又指向了null，第一个if成立，所以会使用cas把newNode挂到p的next，此时p!=t,所以casTail(t, newNode);会执行，然后跳出,此时链表如下：

add(“王五”)

进入for的指针如下图：

此时q==null，所以会使用cas把newNode挂到p的next，此时p==t,所以casTail(t, newNode);不会执行，然后跳出,此时链表如下：

add()方法中p==q判断何时进

Node q = p.next;q是p的next，如果p==q的话说明p.next=p。这种情况在元素出队的情况下会出现，为了是帮助gc，在多线程操作的情况下add在从tail加元素是tail元素被其他线程出队了，此时就要不重新读取新的tail，要不就从head从新开始操作（p = (t != (t = tail)) ? t : head;）

总结：

add过程实际就是不停就是在单链表不断挂新元素的过程，挂next元素时使用了cas来保证线程的安全性，而且不是每次add都会移动tail指针，而是tail已经不是现在的最后一个node时才会移动tail指针

poll()方法

Node h = head, p = h, q;

此时p的item是null，所以先会执行q = p.next

q显然不是null,p也不等于q，所以会执行p=q:

此时item不为null，就会执行item != null && p.casItem(item, null)，就是通过cas把node的item设置为null，如果设置成功则判断p != h，显然是成立的，则执行updateHead(h, ((q = p.next) != null) ? q : p);这个方法不复杂实际就是把head指针指向了p的下一个节点，然后把之前的head的next指针指向自己，帮助gc,最后链表就变成了如图：

peek()方法

跟poll()方法差不多，只是不会删除第一个元素

size()方法

实际就是遍历了这个链表，在遍历时会挪动head指针，使head指针指向第一个元素的node，因为都是无锁操作，所以size可能会不准确

iterator()方法

通过hasNext()方法判断nextNode变量是否为null，为null说明就遍历到了链表最后一个node，再通过next()方法挪动指针依次遍历链表元素。因为都是无锁操作，遍历时可能会读到已经被删除的元素