Java之集合(十七)ConcurrentLinkedQueue

  转载请注明源出处:http://www.cnblogs.com/lighten/p/7491057.html

1.前言

  ConcurrentLinkedQueue是一个*的线程安全队列,遵循FIFO先进先出的原则。头元素就是队列中存在最长时间的一个元素,即插入元素都是尾插入。检索是从头元素开始,不允许存在空元素。迭代器是弱一致性的,不会抛出并发异常。注意:size方法不是一个线性时间操作,这是由于队列的特点,需要遍历统计,如果遍历过程中有修改,就可能得到错误的结果(如果不是需要具体值,一般使用isEmpty来判断,比size>0快)。此外,bulk操作,即addAll,removeAll,retainAll,containsAll和equals,toArray这些方法不保证原子性。

2.ConcurrentLinkedQueue

2.1 数据结构

  数据结构非常简单,就只有一个head和一个tail的Node类型头尾节点,所以其size方法是遍历出来的,由于没有加锁,所以该size实际上可能不正确。

Java之集合(十七)ConcurrentLinkedQueue

  Node节点也十分的简单,只有一个值和下一个节点的引用。不过其替换都是通过CAS操作完成的。

Java之集合(十七)ConcurrentLinkedQueue

  头尾结点初始化为一个值为null的结点。

2.2 基本操作

  添加一个元素:

Java之集合(十七)ConcurrentLinkedQueue

  第一时间就将tail节点赋值给t,t就是当前时刻的一个快照。先从单线程开始理解,先插入一个元素1,这个时候q==null,设置p的next为元素1,注意此时tail节点并没有被改变。再插入一个元素2,由于tail没有改变,所以p不为null,p = q = 元素1进入下一个循环,元素1的后面节点为null,所以元素2被设置为元素1的next,此时p!=t,重置元素尾。由这个过程可以看出,tail并不是第一时间进行改变,而是要隔一个以上进行变化。多线程下就存在插队的情况了,被插队了还需要判断是否被插入了多个队,尾结点被改变了就被插入两个并改变了,就需要以最新的尾结点进行循环尝试插入,否则就选择后面一个节点。p==q的情况发生在poll操作的时候:假设队列中只有二个节点,但是在重新定义tail节点的时候被其它线程抢占了,此时head和tail都没有改变。A线程再插入一个元素,此时t=tail,p=tail,在q赋值的时候暂停了,这里要明白head与tail是相等的,是为null的结点。B线程执行poll操作,poll第一次头结点元素是null,不是我们需要的,再次循环,找到元素1。元素1更新头结点的时候,队列的head变成了元素2,但是head的next(null节点)变成了head自己。这个时候回到A线程,tail=head的,q=tail.next=tail=p,就是这样产生的p等于q。如果还没明白参考文章:这里

  取出一个元素:

Java之集合(十七)ConcurrentLinkedQueue

  这里在上面也描述了一些。poll设置头结点也是要跳过一个才会设置头结点。理解了这个,这段代码也就没什么了,也就是通过CAS进行保证线程安全。这里p==q的情况就更简单了,就是offer的情况,不过是同时有两个线程poll而已,B线程成功了,C线程失败了就会产生p==q的情况。

  其它的方法就不再进行描述了。该集合使用的时候还是需要注意的,使用不当效率反而会下降。再给一篇参考文章:这里

上一篇:虚拟IP(VIP)


下一篇:BZOJ3688: 折线统计