并发包下的linkedBlockingQueue和ConcurrentLinkedQueue的区别是什么?我们先带着这个问题慢慢读源码:先来看看类层次结构,基本上和ConcurrentLinkedQueue差不多,唯一不同的是后者是非阻塞的。
第一步:从全局属性推测功能
第一个capacity是一个容量,也就是可以设置我们阻塞队列链条的长度,第二个是一个原子的计数器,从英文解释来看用来统计元素个数,第三个是头节点,第四个指向尾节点,然后这里维护了2把锁,获取锁,非空condition,添加锁,非满condition。
通过第二张图的Node对象的属性可以知道,这个队列是单向队列,其实并发包下对linked队列都同时提供了双向队列,LinkedBlockingDeque、ConcurrentLinkedDeque。同时对阻塞的链表队列还提供了一个LinkedTransferQueue。这个具体功能再开一个帖子来写。
第二步:构造函数
从上图可以看出,默认情况下我们的队列容量是最大值,也可以通过带参数的来进行设置,然后同时初始化一个null节点,并把头和尾都指向这个节点。
第三步:添加方法,也同时提供了4个方法
add 成功返回true, 失败抛出异常
put成功返回true,不然阻塞直到成功
offer提供了2个重载,一个是成功true,失败返回false,还有一个可以设置阻塞时间,阻塞时间内成功true,失败返回false。
先来看add方法,add方法调用的是abstractQuere的add方法,和ArrayBlockingQueue是一样的,也是通过调用offer方法,如果返回false抛出异常,或者成功。
offer方法源码如下图,通过原子计数器进行容量统计,如果和容量一样,则返回false,如果不等于则把元素包装成node,然后在锁内通过enqueue方法完成添加操作,最后释放锁,同时对追加后的容量判断,如果不满则调用非满唤醒,如果元素个数为0则调用非空唤醒。
在添加的方法里很简单,就是把last,和last.next都指向新加入的节点
下面是带阻塞时间的offer方法,首先如果满了的情况下,调用带时间参数的阻塞方法阻塞,然后阻塞时间结束后,如果有空位置,则加入,如果没有则直接返回false。同样需要对非满进行唤醒,这里的c默认开始是-1,当用c=count.getAndIncrement()方法后,相当于对c进行了+1操作,然后为0,代表此时添加一条数据成功,所以c变为0,然后进行非空唤醒。
下面是Put方法,这里如果满的时候就会一致阻塞,直到其他取出操作唤醒。
下面来看取出和删除的各种方法
take方法会阻塞到能取出一个为止,从head取出,同时从链条中删除
poll方法会从head开始取出一个,同时从链条中删除,还有一个可以设定阻塞时间的重载方法,可以设定一定时间内娶不到则返回。
peek方法直接返回当前head,但是不会删除
remove方法,从head移除一个,如果没有则抛出异常
renmove还可以指定移除一个。如果没有则抛出异常
下面是tabke方法,通过取锁,先获得锁,然后如果链条为空则阻塞,直到存入操作唤醒这个阻塞,然后用dequeue方法获取一个,同时对统计数减一操作,然后做其他唤醒操作。
dequeue方法也是一样的,首先拿到head节点,然后把head指向下一个节点,同时把取出来的节点的下一个节点指向自己,这样关闭了链条,可以帮助GC回收,然后取出更新后头节点的对象,然后把头结点的item设置为Null,由此可以看到头节点的item一直是Null,然后next指向的才是有item对象的节点。也就是头结点其实是个Null。
poll方法则是如果成功返回对象,失败返回null,由下图源码可以看到,如果链条为空直接返回null,如果不为空,利用锁直接去到第一个节点返回。
peek方法是仅仅返回第一个节点的item,并不从链条里移除。
带有阻塞时间的poll方法会根据设定时间阻塞,超时后有则返回对象,没有则返回null。
remove方法直接调用的poll,如果返回Null则抛出异常。
指定移除则是从头开始遍历节点,直到发现为止,然后直接把上一个节点的next指向当前满足条件的next,然后将满足条件的节点的item设置为null。
但是我们发现,p.next对下一个的引用还没有解除,这里不知道为什么不解除?
下面我们看看其他一些API
size方法返回当前链条中的节点个数
clear方法则是一个把取和存的锁都锁上,然后遍历删除,最后解锁
element直接返回第一个节点,同时不进行删除
判断是不是空也直接用我们的原子计数器
查询链条中是否包含某个对象,也是同时上2把锁。
基本上常用的方法我们已经读完了。这里我们做一个总结
链式队列采用的是2把锁,一把写锁,一把取锁。这样就能实现取取互斥,写写互斥,写取不互斥。
因为取总是从头部开始,而写总是从尾部开始,这种情况下对于并发不同操作能够提供更好的支持,这里要对比数组队列为什么是一把锁呢? 数组队列其实是一个环形实现,操作也是同步从头开始,然后环形回绕。
从锁性能上来说,肯定是链条的更优化,但是我们知道数组底层在内存中是连续的,一次读入一个缓存行,一个缓存行存有多个数据,这样能减少CPU与内存的交互,
但是链条在内存中不一定是连续的,每次取下一个位置都需要去内存中读取。CPU和内存会频繁交互
二者都是有界的,可以根据需求不同定性选择。