PriorityBlockingQueue 介绍

Stella981
• 阅读 738

PriorityBlockingQueue是一个基于优先级堆的无界的并发安全的优先级队列(FIFO),队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。

实现原理

PriorityBlockingQueue通过使用堆这种数据结构实现将队列中的元素按照某种排序规则进行排序,从而改变先进先出的队列顺序,提供开发者改变队列中元素的顺序的能力。队列中的元素必须是可比较的,即实现Comparable接口,或者在构建函数时提供可对队列元素进行比较的Comparator对象。

结构介绍

PriorityBlockingQueue通过内部组合PriorityQueue的方式实现优先级队列(private final PriorityQueueq;),另外在外层通过ReentrantLock实现线程安全,同时通过Condition实现阻塞唤醒。

常用方法介绍

PriorityBlockingQueue继承自AbstractQueue,以及实现了BlockingQueue接口,是一个阻塞队列,主要方法:offer(E)/poll()/poll(long, TimeUnit)/take()/remove(Object)。下面我们结合源码堆这些方法进行深入分析。

offer(E)

入队操作。此处虽然PriorityBlockingQueue是阻塞队列,但是其并没有阻塞的入队方法,因为该队列是无界的,所以入队是不会阻塞的。

offer()方法正如在结构介绍中提到的通过组合的方式,通过外部加锁内部直接调用PriorityQueue的offer()方法。所以主要的工作在PriorityQueue内部。

入队时通过调用ReentrantLock.lock()进行加锁,然后调用PriorityQueue.offer()方法进行入队操作,最后通过Condition.signal()唤醒等待其上的线程。PriorityQueue.offer()方法将元素插入到队列的最后,然后自上而下调整堆。

poll()和poll(long, TimeUnit),take()

出队操作。poll(long, TimeUnit)是poll()的阻塞版本,同时take()是无限阻塞版poll()(即无期限阻塞,直到获取到数据),通过Condition.awaitNanos()实现阻塞。三者实现主要逻辑相同,只是在等待时不同,这里主要介绍poll(long, TimeUnit)。

具体的出队操作依然是调用PriorityQueue.poll()。

基本操作原理见代码注释,同时可参考博客:数据结构系列——堆进行详细的了解。

remove(Object)

删除其实并不是常用的方法,主要是堆在删除时还是有点值得介绍的。这里我们直接看PriorityQueue.remove()方法。

当删除堆中的一个元素时,将堆的最后一个元素移动到被删除的位置,然后将最后一个位置值为NULL,当把最后一个元素移动到堆中的某个位置时,这时首先需要从该位置开始自上而下的调整堆,如果该位置的元素在调整时发生变化,即堆有变化,则说明该元素是大于其子节点的,那么该节点就不可能小于其上的父节点(因为堆的结构是传递性的,即子节点小于父节点,其孙子节点同时小于其父节点),所以就不需要再网上调整了;但是如果未发生变化,则说明该位置的节点小于其子节点,那么就无法保证其一定比父节点大,所以需要从该节点开始自上而下的调整堆。调整堆的方法是入队和出队时都有介绍,这里就不介绍了。

以上即PriorityBlockingQueue常用的一些方法,另外一些peek(),迭代等方法就不介绍了,毕竟不涉及堆的改变。

使用场景

PriorityBlockingQueue与普通阻塞队列的不同之处就是在于其支持对队列中的元素进行比较,而决定出队的顺序,所以可以使用PriorityBlockingQueue实现高优先级的线程优先执行。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
2年前
java优先队列PriorityQueue修改队列内元素排序问题
今天发现了新大陆。我以前一直以为,PriorityQueue队列是基于堆排序的不断更新排序的,没错,它是不断更新排序的。但是前提是要插入(删除)数据,如果仅仅是修改已经稳定队列的值或内容,而不进行插入或者删除,那么,这个顺序是不会变的。举个例子:importjava.util.Comparator;i
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Stella981 Stella981
2年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Wesley13 Wesley13
2年前
Java Collection
总结1.优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素,C的优先队列每次取最大元素)。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(_naturalordering_),也可以通过构造时传入的比较器(_Comparator_,类似于C的仿函数)。2.Java中Prio
Wesley13 Wesley13
2年前
04.JUC 集合
基本概念LinkedBlockingQueue是一个用链表实现的有界阻塞队列。LinkedBlockingQueue按照先进先出的原则对元素进行排序。LinkedBlockingQueue采用了双锁、双条件队列来提高读写效率。内部构造LinkedBlockingQueue内部维
Stella981 Stella981
2年前
LinkedBlockingQueue 介绍
LinkedBlockingQueue是一个基于已链接节点的、范围任意的blockingqueue。此队列按FIFO(先进先出)排序元素。队列的头部是在队列中时间最长的元素。队列的尾部是在队列中时间最短的元素。新元素插入到队列的尾部,并且队列获取操作会获得位于队列头部的元素。链接队列的吞吐量通常要高于基于数组的队列,但是在大多数并发应用程序中,其可
Stella981 Stella981
2年前
BlockingQueue介绍
几种类型的BlockingQueueArrayBlockingQueue:一个由数组结构组成的有界阻塞队列。LinkedBlockingQueue:一个由链表结构组成的有界阻塞队列。PriorityBlockingQueue:一个支持优先级排序的无界阻塞队列。DelayQueue:一个使用优先级队列实现的无界阻塞队列。Synchro