首页
学习
活动
专区
工具
TVP
发布

Java并发ConcurrentLinkedQueue源码学习与总结

今天来学习Java中支持并发的链表队列ConcurrentLinkedQueue。ConcurrentLinkedQueue特点

重点说在前面,先直接说根据源码总结出来的重点,然后再来分析,ConcurrentLinkedQueue主要特写如下:

底层数据结构是基于链表的无边界的队列,采用的是FIFO(先进先出)原则排序,使用CAS方式实现线程安全。

属性与构造介绍

ConcurrentLinkedQueue的属性与构造函数如下图:

属性就两个head、tail,由这两个属性来组成ConcurrentLinkedQueue的底层链表结构。head与tail的类型都是内部类Node,Node中有属性item和next,item表示当前Node对象存储的值,next表示当前Node对象的下一个Node对象。

底层是链表结构的容器前面已经分析了很多个了,底层链表的实现都是这样,一个节点存储一条数据。

在上图中最下面的代码是ConcurrentLinkedQueue的无参构造函数,可以看到基本没有做任何的初始化,只初始化了一个item等于null的Node对象赋值给head和tail。

入队方法

容器最关键的就是入队和出队方法,首先来看入队方法,方法源码如下图:

入队方法最终都是调用offer方法,offer方法第一步就是验证入队对象是否为null,所以ConcurrentLinkedQueue不支持存储null对象。

入队方法实际上主要是靠两步循环调用来实现:

第一步是找到队列中的尾结点;

第二步是尝试把新new出来的节点设置到尾结点的next属性中,如果设置成功那就成功了,如果设置失败则再次调用执行第一步;

总结来说就是:找尾结点、更新尾结点,更新失败就再来一次

出队方法

出队方法源码如下图:

出队方法代码也比较简单,就是拿到头结点判断他的item不等于null(所以容器不支持保存null数据)并且采用CAS方式修改节点的item为null,修改成功则出队成功。

出队方法实际上就是从头结点遍历链表,只要遍历节点的item不为null就尝试设置为null,设置成功了就表示获取到当前的item了,设置失败则说明其他线程已经修改了。

出队、入队方法中都有p==q的代码,也就是当前节点与他的子节点是同一个对象的情况,而出现的原因就在于出队方法中的updateHead方法,它会把老节点的next指向他自己,通过这样处理可以是节点离开链表,不能设置为null是因为其他线程拿到会认为是尾结点

总结

前面还学习了很对阻塞队列,其中一些队列与ConcurrentLinkedQueue的功能很像,并且底层实现也很像。只不过阻塞队列是通过加锁来保证线程安全并阻塞线程,而ConcurrentLinkedQueue是通过CAS方式实现,而CAS方式实现就会出现多个线程修改同一处数据的问题,需要考虑到各种特殊情况。

所以ConcurrentLinkedQueue在一些关键地方做了特殊处理,比如更新头结点的时候老的头结点自己指向了自己,而出队、入队都要对这种情况进行处理。

由于会出现多线程更新,所以方法里出现很多多层验证。

Java程序员日常学习笔记,如理解有误欢迎各位交流讨论!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20201018A0BWOM00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券