ConcurrentLinkedQueue
    单向链表
    无锁的,通过CAS来实现线程安全,不用切换线程上下文,但是再并发大的时候会导致线程一直自旋使CPU飙高
    内部维护了一个head和一个tail两个node节点,其中再添加元素的时候tail节点不是每次添加玩都会去移动,是每入队两次tail才移动一次,这样减少了tail的移动次数,tail.next == null 那么tail就是真正的尾节点(如果tail直接指向尾节点的话因为设置tail是CAS操作,性能上不如两次移动一次)

    1. public boolean offer(E e) {
    2. checkNotNull(e);
    3. final Node<E> newNode = new Node<E>(e);
    4. for (Node<E> t = tail, p = t;;) {
    5. Node<E> q = p.next;
    6. if (q == null) {
    7. // p is last node
    8. if (p.casNext(null, newNode)) {
    9. // Successful CAS is the linearization point
    10. // for e to become an element of this queue,
    11. // and for newNode to become "live".
    12. if (p != t) // hop two nodes at a time
    13. // 这里设置移动tail节点,第一次p == t 就不会设置tail节点
    14. casTail(t, newNode); // Failure is OK.
    15. return true;
    16. }
    17. // Lost CAS race to another thread; re-read next
    18. }
    19. else if (p == q) // p.next = p 并发下可能会p.next = p
    20. // We have fallen off list. If tail is unchanged, it
    21. // will also be off-list, in which case we need to
    22. // jump to head, from which all live nodes are always
    23. // reachable. Else the new tail is a better bet.
    24. p = (t != (t = tail)) ? t : head;
    25. else
    26. // Check for tail updates after two hops.
    27. p = (p != t && t != (t = tail)) ? t : q;
    28. }
    29. }