欢迎光临
我们一直在努力

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

我们知道线程Thread可以调用setPriority(int newPriority)来设置优先级的,线程优先级高的线程先执行,优先级低的后执行。而前面介绍的ArrayBlockingQueue、LinkedBlockingQueue都是采用FIFO原则来确定线程执行的先后顺序,那么有没有一个队列可以支持优先级呢? PriorityBlockingQueue 。

PriorityBlockingQueue是一个支持优先级的无界阻塞队列。默认情况下元素采用自然顺序升序排序,当然我们也可以通过构造函数来指定Comparator来对元素进行排序。需要注意的是PriorityBlockingQueue不能保证同优先级元素的顺序。

二叉堆

由于PriorityBlockingQueue底层采用二叉堆来实现的,所以有必要先介绍下二叉堆。

二叉堆是一种特殊的堆,就结构性而言就是完全二叉树或者是近似完全二叉树,满足树结构性和堆序性。树机构特性就是完全二叉树应该有的结构,堆序性则是:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。它有两种表现形式:最大堆、最小堆。

最大堆:父节点的键值总是大于或等于任何一个子节点的键值(下右图)

最小堆:父节点的键值总是小于或等于任何一个子节点的键值(下走图)

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

二叉堆一般用数组表示,如果父节点的节点位置在n处,那么其左孩子节点为:2 * n + 1 ,其右孩子节点为2 * (n + 1),其父节点为(n – 1) / 2 处。上左图的数组表现形式为:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

二叉堆的基本结构了解了,下面来看看二叉堆的添加和删除节点。二叉堆的添加和删除相对于二叉树来说会简单很多。

添加元素

首先将要添加的元素N插添加到堆的末尾位置(在二叉堆中我们称之为空穴)。如果元素N放入空穴中而不破坏堆的序(其值大于跟父节点值(最大堆是小于父节点)),那么插入完成。否则,我们则将该元素N的节点与其父节点进行交换,然后与其新父节点进行比较直到它的父节点不在比它小(最大堆是大)或者到达根节点。

假如有如下一个二叉堆

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

这是一个最小堆,其父节点总是小于等于任一一个子节点。现在我们添加一个元素2。

第一步:在末尾添加一个元素2,如下:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

第二步:元素2比其父节点6小,进行替换,如下:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

第三步:继续与其父节点5比较,小于,替换:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

第四步:继续比较其跟节点1,发现跟节点比自己小,则完成,到这里元素2插入完毕。所以整个添加元素过程可以概括为:在元素末尾插入元素,然后不断比较替换直到不能移动为止。

复杂度:Ο(logn)

删除元素

删除元素与增加元素一样,需要维护整个二叉堆的序。删除位置1的元素(数组下标0),则把最后一个元素空出来移到最前边,然后和它的两个子节点比较,如果两个子节点中较小的节点小于该节点,就将他们交换,知道两个子节点都比该元素大为止。

就上面二叉堆而言,删除的元素为元素1。

第一步:删掉元素1,元素6空出来,如下:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

第二步:与其两个子节点(元素2、元素3)比较,都小,将其中较小的元素(元素2)放入到该空穴中:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

第三步:继续比较两个子节点(元素5、元素7),还是都小,则将较小的元素(元素5)放入到该空穴中:!

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

第四步:比较其子节点(元素8),比该节点小,则元素6放入该空穴位置不会影响二叉堆的树结构,放入:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

到这里整个删除操作就已经完成了。

二叉堆的添加、删除操作还是比较简单的,很容易就理解了。下面我们就参考该内容来开启PriorityBlockingQueue的源代码研究。

PriorityBlockingQueue

PriorityBlockingQueue继承AbstractQueue,实现BlockingQueue接口。

public class PriorityBlockingQueue<E> extends AbstractQueue<E>
 implements BlockingQueue<E>, java.io.Serializable

定义了一些属性:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

内部仍然采用可重入锁ReentrantLock来实现同步机制,但是这里只有一个notEmpty的Condition,了解了ArrayBlockingQueue我们知道它定义了两个Condition,之类为何只有一个呢?原因就在于PriorityBlockingQueue是一个无界队列,插入总是会成功,除非消耗尽了资源导致服务器挂。

入列

PriorityBlockingQueue提供put()、add()、offer()方法向队列中加入元素。我们这里从put()入手:put(E e) :将指定元素插入此优先级队列。

 public void put(E e) {
 offer(e); // never need to block
 }

PriorityBlockingQueue是无界的,所以不可能会阻塞。内部调用offer(E e):

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

siftUpComparable

当比较器comparator为null时,采用自然排序,调用siftUpComparable方法:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

这段代码所表示的意思:将元素X插入到数组中,然后进行调整以保持二叉堆的特性。

siftUpUsingComparator

当比较器不为null时,采用所指定的比较器,调用siftUpUsingComparator方法:

 private static <T> void siftUpUsingComparator(int k, T x, Object[] array,
 Comparator<? super T> cmp) {
 while (k > 0) {
 int parent = (k - 1) >>> 1;
 Object e = array[parent];
 if (cmp.compare(x, (T) e) >= 0)
 break;
 array[k] = e;
 k = parent;
 }
 array[k] = x;
 }

扩容:tryGrow

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

整个添加元素的过程和上面二叉堆一模一样:先将元素添加到数组末尾,然后采用“上冒”的方式将该元素尽量往上冒。

出列

PriorityBlockingQueue提供poll()、remove()方法来执行出对操作。出对的永远都是第一个元素:array[0]。

 public E poll() {
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
 return dequeue();
 } finally {
 lock.unlock();
 }
 }

先获取锁,然后调用dequeue()方法:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

siftDownComparable

如果比较器为null,则调用siftDownComparable来进行自然排序处理:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

处理思路和二叉堆删除节点的逻辑一样:就第一个元素定义为空穴,然后把最后一个元素取出来,尝试插入到空穴位置,并与两个子节点值进行比较,如果不符合,则与其中较小的子节点进行替换,然后继续比较调整。

siftDownUsingComparator

如果指定了比较器,则采用比较器来进行调整:

【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

 

PriorityBlockingQueue采用二叉堆来维护,所以整个处理过程不是很复杂,添加操作则是不断“上冒”,而删除操作则是不断“下掉”。掌握二叉堆就掌握了PriorityBlockingQueue,无论怎么变还是。对于PriorityBlockingQueue需要注意的是他是一个无界队列,所以添加操作是不会失败的,除非资源耗尽。

 收藏 (0) 打赏

您可以选择一种方式赞助本站

支付宝扫一扫赞助

微信钱包扫描赞助

未经允许不得转载:英协网 » 【死磕Java并发】—–J.U.C之阻塞队列:PriorityBlockingQueue

分享到: 生成海报
avatar

热门文章

  • 评论 抢沙发

    • QQ号
    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    登录

    忘记密码 ?

    切换登录

    注册

    我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活