Skip to main content

moregeek program

源码角度了解concurrentlinkedqueue_周杰伦本人的博客-多极客编程

源码角度了解ConcurrentLinkedQueue


ConcurrentLinkedQueue是基于链表的线程安全的队列,队列遵循先进先出的策略,新元素插入到尾部,获取元素获取的是队列的头部元素,队列的元素不可以为null


一开始头部指针和尾部指针都指向null


入队列方法offer()方法


offer()方法是将元素插入队列尾部,因为队列是没有界限的,这个方法永远不会返回false


public boolean offer(E e) {
checkNotNull(e);
final Node<E> newNode = new Node<E>(e);

for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
// p is last node
if (p.casNext(null, newNode)) {
if (p != t) // hop two nodes at a time
casTail(t, newNode); // Failure is OK.
return true;
}
}
else if (p == q)
p = (t != (t = tail)) ? t : head;
else
p = (p != t && t != (t = tail)) ? t : q;
}
}


  1. 根据传入的元素e创建新的节点
  2. for循环,获取tail指针指向的节点,判断是否为尾结点,如果是尾结点,添加节点到尾部。一开始p和tail相等,q=p.next,q为null表示p指向的是尾结点,就可以添加新的节点到尾部了,调用casNext()方法让p的next指向新的节点,新节点的next是q
  3. 再添加节点的时候p同样指向了尾结点,p的下一个节点有指向新的节点,而tail指针指向的是倒数第二个元素,此时p指向倒数第二个节点,tail指向倒数第三个节点,p和tail不相等,调用casTail()更xin tail指向的节点为最新节点,也就是tail指向了最后一个节点。
  4. 入队两个节点后更新一次tail指针,失败也无所谓,然后返回true,只要保证p的下一个指针指向新节点就可以。
  5. 如果不是尾结点改变p的值,进一步for循环直到达到尾结点

出队列方法poll()方法


public E poll() {
restartFromHead:
for (;;) {
for (Node<E> h = head, p = h, q;;) {
E item = p.item;

if (item != null && p.casItem(item, null)) {
if (p != h) // hop two nodes at a time
updateHead(h, ((q = p.next) != null) ? q : p);
return item;
}
else if ((q = p.next) == null) {
updateHead(h, p);
return null;
}
else if (p == q)
continue restartFromHead;
else
p = q;
}
}
}

出队列和入队列的逻辑差不多



  1. 使用p指针指向头部节点,也就是说p=head q=p.next 此时p和q不相等,如果节点的值不为空,就可以出队列了,调用casItem()方便改变p的值,设置为null,此时p和head相等,并不更新head指针
  2. 当再有元素出队列的时候,p=head,head指向的元素已经是null,此时p.item为空,p移动到q指向的位置,再循环获取到的p.item不为空,设置为null,输出元素,此时p和head不相等,更新head指针指向的元素,head指针每出队列两个元素更新一次

空队列的判断


我们了解到,head指针和tail指针并不一定指向头结点和尾结点,我们怎么判断这个队列是不是空队列呢,我们看一下它的isEmpty()方法


public boolean isEmpty() {
return first() == null;
}

first()是从head指针指向的位置查找返回第一个不是null的元素,如果遍历完都是没有找到,返回null,此时isEmpty()方法就返回true了


总结


这篇文章讲了ConcurrentLinkedQueue的实现原理,它通过CAS来保证线程安全,head tail指针每两个元素的入队和出队才会更新一次,我们介绍了一下它的入队方法offer()和出队方法poll()的实现,已经如何判断队列为空


❤️ 感谢大家


如果你觉得这篇内容对你挺有有帮助的话:



  1. 欢迎关注我❤️,点赞👍🏻,评论🤤,转发🙏
  2. 关注盼盼小课堂,定期为你推送好文,还有群聊不定期抽奖活动,可以畅所欲言,与大神们一起交流,一起学习。
  3. 有不当之处欢迎批评指正。

©著作权归作者所有:来自51CTO博客作者周杰伦本人的原创作品,请联系作者获取转载授权,否则将追究法律责任

源码角度了解concurrenthashmap_周杰伦本人的博客-多极客编程

源码角度了解ConcurrentHashMap ConcurrentHashMap大家都知道,它的数据结构前期是链表后期是红黑树,我们通过节点类型是Node节点和TreeNode节点可以知道它目前的结构是链表还是红黑树,ConcurrentHashMap为什么使用红黑树呢?说白了,当元素变多的时候,红黑树能有更好的查询和更新速度,还能解决Hash冲突的问题 ConcurrentHashMap是使用

#yyds干货盘点# leetcode 热题 hot 100:下一个排列_灰太狼_cxh的博客-多极客编程

题目:整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。

#yyds干货盘点# 面试必刷top101:字符串的排列_风的博客-多极客编程

1.简述:描述输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。数据范围:要求:空间复杂度 ,时间复杂度 输入描述:输入一个字符串,长度不超过10,字符只包括大小写字母。示例1输入:"ab"返回值:["ab","ba"]说明:返回["ba

lambda表达式详解_生而为人的博客-多极客编程

Lambda表达式和匿名函数作用一样,相当于传递一个方法,只是更简单。应用于通常是指需要一个函数,但是又不想费神去命名一个函数的场合下使用。如果说,⼀个接口中,要求实现类必须实现的抽象方法,有且只有⼀个!这样的接口,就是函数式接口。一、语法格式定义标准格式:(parameter)->{expression or statement},Lambda表达式组成三要素:括号,箭头,代码块。Lamb

行为型设计模式之责任链模式_积跬步,至千里。的博客-多极客编程

责任链模式 责任链模式(Chain of Responsibility Pattern)属于行为型模式。 它是将链中每一个节点看作是一个对象,每个节点处理的请求均不同,且内部自动维护一个下一节点对象。当一个请求从链式的首端发出时,会沿着链的路径依次传递给每一个节点对象,直至有对象处理这个请求为止。 应用场景 责任链模式主要是解耦请求与处理,客户只需将请求发送到链上即可,无需关心请求的具

intellij idea 的project structure说明_是文渡呀的博客-多极客编程

IntelliJ IDEA 的Project structure可以在File->Project structure中打开,同时,在新建项目是IDE一般用向导的方式让你填写Project structure相关内容。在说明如何填写之前,先说说这些项都代表什么,包含Project、module、library、artficat和facet。project就是这个工程,下面有很多module。这

源码角度了解concurrenthashmap_周杰伦本人的博客-多极客编程

源码角度了解ConcurrentHashMap ConcurrentHashMap大家都知道,它的数据结构前期是链表后期是红黑树,我们通过节点类型是Node节点和TreeNode节点可以知道它目前的结构是链表还是红黑树,ConcurrentHashMap为什么使用红黑树呢?说白了,当元素变多的时候,红黑树能有更好的查询和更新速度,还能解决Hash冲突的问题 ConcurrentHashMap是使用

#yyds干货盘点# leetcode 热题 hot 100:下一个排列_灰太狼_cxh的博客-多极客编程

题目:整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。

#yyds干货盘点# 面试必刷top101:字符串的排列_风的博客-多极客编程

1.简述:描述输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。数据范围:要求:空间复杂度 ,时间复杂度 输入描述:输入一个字符串,长度不超过10,字符只包括大小写字母。示例1输入:"ab"返回值:["ab","ba"]说明:返回["ba

lambda表达式详解_生而为人的博客-多极客编程

Lambda表达式和匿名函数作用一样,相当于传递一个方法,只是更简单。应用于通常是指需要一个函数,但是又不想费神去命名一个函数的场合下使用。如果说,⼀个接口中,要求实现类必须实现的抽象方法,有且只有⼀个!这样的接口,就是函数式接口。一、语法格式定义标准格式:(parameter)->{expression or statement},Lambda表达式组成三要素:括号,箭头,代码块。Lamb

行为型设计模式之责任链模式_积跬步,至千里。的博客-多极客编程

责任链模式 责任链模式(Chain of Responsibility Pattern)属于行为型模式。 它是将链中每一个节点看作是一个对象,每个节点处理的请求均不同,且内部自动维护一个下一节点对象。当一个请求从链式的首端发出时,会沿着链的路径依次传递给每一个节点对象,直至有对象处理这个请求为止。 应用场景 责任链模式主要是解耦请求与处理,客户只需将请求发送到链上即可,无需关心请求的具

intellij idea 的project structure说明_是文渡呀的博客-多极客编程

IntelliJ IDEA 的Project structure可以在File->Project structure中打开,同时,在新建项目是IDE一般用向导的方式让你填写Project structure相关内容。在说明如何填写之前,先说说这些项都代表什么,包含Project、module、library、artficat和facet。project就是这个工程,下面有很多module。这