首页 > 其他分享 >多线程篇(阻塞队列- PriorityBlockingQueue)(持续更新迭代)

多线程篇(阻塞队列- PriorityBlockingQueue)(持续更新迭代)

时间:2024-09-09 12:25:31浏览次数:10  
标签:迭代 队列 元素 入队 出队 array 多线程 节点 PriorityBlockingQueue

目录

一、简介

二、类图

三、源码解析

1. 字段讲解

2. 构造方法

3. 入队方法

put

浮调整比较器方法的实现

入队图解

4. 出队方法

take

dequeue

下沉调整比较器方法的实现

出队图解

四、总结


一、简介

PriorityBlockingQueue队列是 JDK1.5 的时候出来的一个阻塞队列。但是该队列入队的时候是不会阻塞的,

永远会加到队尾。

下面我们介绍下它的几个特点:

  • PriorityBlockingQueue 和 ArrayBlockingQueue 一样是基于数组实现的,但后者在初始化时需要指定长

度,前者默认长度是 11。

  • 该队列可以说是真正的无界队列,它在队列满的时候会进行扩容,而前面说的无界阻塞队列其实都有有界,只

是界限太大可以忽略(最大值是 2147483647)

  • 该队列属于权重队列,可以理解为它可以进行排序,但是排序不是从小到大排或从大到小排,是基于数组的堆

结构(具体如何排下面会进行分析)

  • 出队方式和前面的也不同,是根据权重来进行出队,和前面所说队列中那种先进先出或者先进后出方式不同。
  • 其存入的元素必须实现Comparator,或者在创建队列的时候自定义Comparator

注意:

  1. 堆结构实际上是一种完全二叉树,建议学习前了解一下二叉树。
  2. 堆又分为大顶堆和小顶堆。大顶堆中第一个元素肯定是所有元素中最大的,小顶堆中第一个元素是所有元素中

最小的。

二、类图

三、源码解析

1. 字段讲解

从下面的字段我们可以知道,该队列可以排序,使用显示锁来保证操作的原子性,

在空队列时,出队线程会堵塞等。

    /**
    * 默认数组长度
    */
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * 最大达容量,分配时超出可能会出现 OutOfMemoryError 异常
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 队列,存储我们的元素
     */
    private transient Object[] queue;

    /**
     * 队列长度
     */
    private transient int size;

    /**
     * 比较器,入队进行权重的比较
     */
    private transient Comparator<? super E> comparator;

    /**
     * 显示锁
     */
    private final ReentrantLock lock;
    
    /**
     * 空队列时进行线程阻塞的 Condition 对象
     */
    private final Condition notEmpty;

2. 构造方法

    /**
    * 默认构造,使用长度为 11 的数组,比较器为空
    */
     public PriorityBlockingQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    /**
    * 自定义数据长度构造,比较器为空
    */
    public PriorityBlockingQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
    /**
    * 自定义数组长度,可以自定义比较器
    */
    public PriorityBlockingQueue(int initialCapacity,
                                 Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.lock = new ReentrantLock();
        this.notEmpty = lock.newCondition();
        this.comparator = comparator;
        this.queue = new Object[initialCapacity];
    }

3. 入队方法

put

入队方法,下面可以看到 put 方法最终会调用 offer 方法,所以我们只看 offer 方法即可。

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

     public boolean offer(E e) {
         //判断是否为空
        if (e == null)
            throw new NullPointerException();
           //显示锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        //定义临时对象
        int n, cap;
        Object[] array;
        //判断数组是否满了
        while ((n = size) >= (cap = (array = queue).length))
            //数组扩容
            tryGrow(array, cap);
        try {
            //拿到比较器
            Comparator<? super E> cmp = comparator;
            //判断是否有自定义比较器
            if (cmp == null)
                //堆上浮
                siftUpComparable(n, e, array);
            else
                //使用自定义比较器进行堆上浮
                siftUpUsingComparator(n, e, array, cmp);
            //队列长度 +1
            size = n + 1;
            //唤醒休眠的出队线程
            notEmpty.signal();
        } finally {
            //释放锁
            lock.unlock();
        }
        return true;
    }

浮调整比较器方法的实现

    private static <T> void siftUpComparable(int k, T x, Object[] array) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            //无符号向左移,目的是找到放入位置的父节点
            int parent = (k - 1) >>> 1;
            //拿到父节点的值
            Object e = array[parent];
            //比较是否大于该元素,不大于就没比较交换
            if (key.compareTo((T) e) >= 0)
                break;
            //以下都是元素位置交换
            array[k] = e;
            k = parent;
        }
        array[k] = key;
    }

根据上面的代码,可以看出这是完全二叉树在进行上浮调整。调整入队的元素,找出最小的,将元素排列有序化。

简单理解就是:父节点元素值一定要比它的子节点得小,如果父节点大于子节点了,那就两者位置进行交换。

入队图解

说的可能很模糊,我们先写个 demo,根据 demo 来进行图解分析:

public class TestPriorityBlockingQueue {
    public static void main(String[] args) throws InterruptedException {
        PriorityBlockingQueue<Integer> concurrentLinkedQueue = new PriorityBlockingQueue<Integer>();
        concurrentLinkedQueue.offer(10);
        concurrentLinkedQueue.offer(20);
        concurrentLinkedQueue.offer(5);
        concurrentLinkedQueue.offer(1);
        concurrentLinkedQueue.offer(25);
        concurrentLinkedQueue.offer(30);
        //输出元素排列
        concurrentLinkedQueue.stream().forEach(e-> System.out.print(e+"  "));
        //取出元素
        Integer take = concurrentLinkedQueue.take();
        System.out.println();
        concurrentLinkedQueue.stream().forEach(e-> System.out.print(e+"  "));
    }
}

上面可以看出,我们要入队的元素是 [10,20,5,1,21,30],接下来我们用图来演示一步步入队情况。

队列初始化时:

这时,我们开始将元素 元素 10 入队,并用二叉树辅助理解:

我们在将元素 20 入队:

将元素 5 入队后发现父节点大于子节点,这时需要进行上浮调整

开始进行上浮调整,将元素 10 和元素 5进行位置调换,结果如下:

接着将元素 1 入队后发现父节点大于子节点,继续进行调整:

第一次调整将元素 20 和元素 1 进行位置交换,交换完毕后结果如下:

交换完毕后,我们发现父节点的元素值还是大于子节点,说明还需要进行一次交换,最后交换结果如下:

接下来将元素 25 和 30 入队,结果如下:

注:

最小堆的的顶端一定是元素值最小的那个。

4. 出队方法

take

出队方法,该方法会阻塞

public E take() throws InterruptedException {
    //显示锁
    final ReentrantLock lock = this.lock;
    //可中断锁
    lock.lockInterruptibly();
    //结果接受对象
    E result;
    try {
        //判读队列是否为空
        while ( (result = dequeue()) == null)
            //线程阻塞
            notEmpty.await();
    } finally {
        lock.unlock();
    }
    return result;
}

dequeue

具体出队方法的实现

 private E dequeue() {
    //长度减少 1
    int n = size - 1;
    //判断队列中是否又元素
    if (n < 0)
        return null;
    else {
        //队列对象
        Object[] array = queue;
        //取出第一个元素
        E result = (E) array[0];
        //拿出最后一个元素
        E x = (E) array[n];
        //置空
        array[n] = null;
        Comparator<? super E> cmp = comparator;
        if (cmp == null)
            //下沉调整
            siftDownComparable(0, x, array, n);
        else
            siftDownUsingComparator(0, x, array, n, cmp);
           //成功则减少队列中的元素数量
        size = n;
        return result;
    }
}

总体就是找到父节点与两个子节点中最小的一个节点,然后进行交换位置,不断重复,由上而下的交换。

下沉调整比较器方法的实现

private static <T> void siftDownComparable(int k, T x, Object[] array,
                                               int n) {
    //判断队列长度
    if (n > 0) {
        Comparable<? super T> key = (Comparable<? super T>)x;
        //找到队列最后一个元素的父节点的索引。
        //如下图最大元素是30 父节点是 10,对于索引是 2
        int half = n >>> 1;           // loop while a non-leaf
        while (k < half) {
            //拿到 k 节点下的左子节点
            int child = (k << 1) + 1; // assume left child is least
            //取得子节点对应的值
            Object c = array[child];
            //取得 k 右子节点的索引
            int right = child + 1;
            //比较右节点的索引是否小于队列长度和左右子节点的值进行比较
            if (right < n &&
                ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
                c = array[child = right];
            //比较父节点值是否大于子节点
            if (key.compareTo((T) c) <= 0)
                break;
            //下面都是元素替换
            array[k] = c;
            k = child;
        }
        array[k] = key;
    }
}

出队图解

这时,我们需要从队列中取出第一个元素 1,元素 1 取出时会与队列中最后一个元素进行交换,并将最后一个元素

置空。(实际上源码不是这么做的,源代码中是用变量来保存索引,直到全部下沉调整完成才进行替换)

替换后,结果就如下图显示一样。我们发现父节点大于子节点了,所以还需要再一次进行替换操作。

再一次替换后,将元素 30 下沉到下一个左边子节点,子节点上浮到原父节点位置。这就完成了下沉调整了。

四、总结

PriorityBlockingQueue 真的是个神奇的队列,可以实现优先出队。

最特别的是它只有一个锁,入队操作永远成功,而出队只有在空队列

的时候才会进行线程阻塞。可以说有一定的应用场景吧,比如:有任务要执行,可以对任务加一个优先级的权重,

这样队列会识别出来,对该任务优先进行出队。

标签:迭代,队列,元素,入队,出队,array,多线程,节点,PriorityBlockingQueue
From: https://blog.csdn.net/qq_51226710/article/details/142047560

相关文章

  • 如何实现标准库般强大的 C++ Vector?:从动态扩容到移动语义到迭代器全覆盖
    在C++中,std::vector是最常用的动态数组容器。它具有高效的内存管理、动态扩容、随机访问等特点。在这篇博客中,我们将从零开始,实现一个功能强大、灵活、并且具有高性能的Vector类,具备std::vector的大部分功能,包括动态扩容、迭代器、模板支持、随机访问等,尽可能模仿C+......
  • 【Java学习】配置文件&日志&多线程
    一、配置文件1、概述在企业开发过程中,我们习惯把一些需要灵活配置的数据放在一些文本文件中,而不是在Java代码写死。我们把这种存放程序配置信息的文件,统称为配置文件。配置文件一般要求有明确的格式,以方便读写操作。2、PropertiesProperties是一个Map集合(键值对集合),但是一......
  • python装饰器\迭代器\生成器
    1.迭代器\生成器#斐波那契数列deffib(n):"""生成斐波那契数列的前n个数字。参数:n--要生成的斐波那契数列的长度返回:生成器,产出斐波那契数列的前n个数字。"""a,b=0,1#初始化斐波那契数列的前两个数字content=......
  • 多线程轮流打印字符
    要求:使用多个线程轮流打印字符方法1。无锁自旋,一般在多核机器并且临界区耗时很短的话可以尝试自旋publicclassprintABC{staticLoggerlog=newLogger(Logger.LogLevel.DEBUG,printABC.class);staticvolatileintcur=0;publicstaticvoidmain(St......
  • 9-迭代器
    迭代器ArrayList<String>list=newArrayList<>();list.add("aa");list.add("bb");list.add("cc");list.add("dd");list.add("ee");......
  • C# 多线程的学习大纲
    C#多线程编程是开发高效并发应用的核心技术之一。以下是一个详细的学习大纲,涵盖了C#多线程编程的各个方面,从基础概念到高级主题。学习大纲1.多线程基础知识1.1什么是线程?定义线程及其在操作系统中的角色进程与线程的区别1.2C#中的多线程基础Thread类的基本使......
  • 多线程篇(阻塞队列- BlockingQueue)(持续更新迭代)
    目录一、了解什么是阻塞队列之前,需要先知道队列1.Queue(接口)二、阻塞队列1.前言2.什么是阻塞队列3.Java里面常见的阻塞队列三、BlockingQueue(接口)1.前言2.简介3.特性3.1.队列类型3.2.队列数据结构2.简介4.核心功能入队(放入数据)出队(取出数据)总结四......
  • [Redis]Redis到底是单线程还是多线程程序?
    概述这里我们先给出问题的全面回答:Redis到底是多线程还是单线程程序要看是针对哪个功能而言,对于核心业务功能部分(命令操作处理数据),Redis是单线程的,主要是指Redis的网络IO和键值对读写是由一个线程来完成的,这也是Redis对外提供键值存储服务的主要流程,所以一般我们认为Red......
  • Java多线程中常见死锁问题及解决方案
    在编写Java多线程代码的时候,很难避免会出现线程安全问题,在线程安全问题中也有一个很常见的现象就是死锁现象。今天我们就来聊一聊Java中的死锁问题,以及如何避免死锁问题。本次知识点讲解建立在大家已经知道“锁”......
  • 【C++】简单易懂的vector迭代器
    一、迭代器的本质vector的迭代器本质上就是一个被封装的指针。迭代器的用法和指针的用法十分相似,就是一个像指针的假指针,我们不妨把迭代器看作一个伪指针。二、迭代器的使用句式(可以看到迭代器和指针很像):迭代器有四种:1、正向迭代器:容器名<类型>::iterator迭代器名2、常......