java中PriorityBlockingQueue的入队知识点总结

下面是对 "java中PriorityBlockingQueue的入队知识点总结" 的详细讲解。

PriorityBlockingQueue的概述

PriorityBlockingQueuejava.util.concurrent 包中的一个类,它是一个具有优先级的无界阻塞队列,可以用来实现生产者-消费者模式中的队列。

PriorityBlockingQueue 使用数组实现,内部采用堆结构排序,可以根据元素自然排序或者通过构造函数指定的 Comparator 排序。它有以下主要特点:

  • 内部采用堆结构实现排序,具有很好的性能。
  • 可以通过两种方式排序:自然排序和指定比较器排序。
  • 内部使用 ReentrantLock(可重入锁)来保证线程安全。

PriorityBlockingQueue的入队操作

PriorityBlockingQueue 的入队方法是 offer()put(),两种方法的区别在于,当队列已满时,offer() 方法会返回 false,而 put() 方法则会阻塞。

offer()方法

offer() 方法可以向队尾插入一个元素,如果队列已满,则返回 false

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);
        size = n + 1;
        notEmpty.signal();
    } finally {
        lock.unlock();
    }
    return true;
}

tryGrow() 方法的作用是扩容。如果队列的长度已经等于容量,说明队列已满,此时需要扩容以容纳新的元素。

扩容的方法是通过创建一个新数组 newArray 来实现的,然后将原数组 queue 的元素复制到新数组中,最后将 newArray 赋值给 queue

private void tryGrow(Object[] array, int oldCap) {
    lock.unlock();
    Object[] newArray = null;
    if (allocationSpinLock == 0 &&
        UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset, 0, 1)) {
        try {
            int newCap = oldCap + ((oldCap < 64) ?
                                   (oldCap + 2) :
                                   (oldCap >> 1));
            if (newCap >= MAX_ARRAY_SIZE)
                throw new OutOfMemoryError();
            int newAlloc = newCap - oldCap;
            newArray = new Object[newCap];
            System.arraycopy(array, 0, newArray, 0, Math.min(array.length, newAlloc));
        } finally {
            allocationSpinLock = 0;
        }
    }
    if (newArray == null)
        Thread.yield();
    lock.lock();
    if (queue == array) {
        queue = newArray;
        System.arraycopy(array, 0, newArray, 0, oldCap);
    }
}

while 循环的作用是,如果队列已满,就不断尝试扩容,直到新增元素可以被添加到队列中。

如果队列已满,但是扩容失败(例如在高并发的情况下,多个线程同时扩容),此时会让出 CPU 时间,等待其他线程释放锁,再重新尝试添加元素。

然后,调用 siftUpComparable()siftUpUsingComparator() 方法来对新增元素进行排序。如果没有指定比较器(即使用默认的自然排序),则调用 siftUpComparable() 方法。

private void siftUpComparable(int k, E x, Object[] array) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = array[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        array[k] = e;
        k = parent;
    }
    array[k] = key;
}

while 循环的条件是:如果新增元素比其父节点更小,则将父节点下移,继续比较,直到满足堆的性质。

最后,更新队列的元素数量,发出 notEmpty 的信号,表示队列已非空,并返回 true

put()方法

put() 方法将一个元素插入队列中,如果队列已满,则一直等待,直到队列有空闲位置。

public void put(E e) throws InterruptedException {
    offer(e); // 向队列尾部插入一个元素
    if (Thread.interrupted()) // 判断线程是否被打断,如果被打断,就抛出异常
        throw new InterruptedException();
}

put() 方法中,调用了 offer() 方法向队列尾部插入元素。如果队列已满,就不断尝试扩容或者等待,直到新增元素可以被添加到队列中。

最后,如果线程被中断,就抛出 InterruptedException 异常。

示例说明

下面以两个示例分别说明 PriorityBlockingQueue 的入队操作。

示例一

PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>(16);

for (int i = 0; i < 20; i++) {
    queue.offer(i);
    System.out.println("add " + i + ", size: " + queue.size());
}

结果输出:

add 0, size: 1
add 1, size: 2
add 2, size: 3
add 3, size: 4
add 4, size: 5
add 5, size: 6
add 6, size: 7
add 7, size: 8
add 8, size: 9
add 9, size: 10
add 10, size: 11
add 11, size: 12
add 12, size: 13
add 13, size: 14
add 14, size: 15
add 15, size: 16
add 16, size: 17
add 17, size: 18
add 18, size: 19
add 19, size: 20

PriorityBlockingQueue 的入队操作中,如果队列已满,就会进行扩容。在这个示例中,队列的初始容量是 16,当添加第 8 个元素时,队列已满,触发了扩容操作。从输出结果可以看出,每插入一个元素,队列的大小就会增加 1 。

示例二

PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>(16);

for (int i = 0; i < 20; i++) {
    queue.put(i);
    System.out.println("add " + i + ", size: " + queue.size());
}

System.out.println("--------------------");

for (int i = 20; i < 30; i++) {
    queue.put(i);
    System.out.println("add " + i + ", size: " + queue.size());
}

结果输出:

add 0, size: 1
add 1, size: 2
add 2, size: 3
add 3, size: 4
add 4, size: 5
add 5, size: 6
add 6, size: 7
add 7, size: 8
add 8, size: 9
add 9, size: 10
add 10, size: 11
add 11, size: 12
add 12, size: 13
add 13, size: 14
add 14, size: 15
add 15, size: 16
add 16, size: 17
add 17, size: 18
add 18, size: 19
add 19, size: 20
--------------------
add 20, size: 21
add 21, size: 22
add 22, size: 23
add 23, size: 24
add 24, size: 25
add 25, size: 26
add 26, size: 27
add 27, size: 28
add 28, size: 29
add 29, size: 30

在这个示例中,向一个容量为 16 的队列中插入了 20 个元素。由于队列的容量瞬间不足,应用了阻塞队列,当添加第 16 个元素时,队列已满,程序被阻塞,等待其他线程从队列中取出元素,直到取出足够的元素、空出足够的空间,才能继续向队列中添加元素。从输出结果可以看出,当队列中的元素个数小于容量时,插入元素的速度比取出元素的速度快;当队列中的元素个数等于容量时,新插入的元素会被阻塞,等待有空余空间的时候再插入。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:java中PriorityBlockingQueue的入队知识点总结 - Python技术站

(0)
上一篇 2023年5月26日
下一篇 2023年5月26日

相关文章

  • SpringBoot雪花算法主键ID传到前端后精度丢失问题的解决

    首先,我们需要了解雪花算法主键ID的生成方式,它会生成一个64bit的整数,其中高42位代表毫秒级时间戳,中间的位数为机器ID和进程ID等信息,低位12位为序列号。因此,我们需要进行精度处理,以避免前端显示时的精度丢失问题。 解决这个问题的方法是将生成的Long类型的主键ID转换为String类型,在传到前端时进行显示。SpringBoot提供了一个注解@J…

    Java 2023年5月20日
    00
  • SpringCloud Feign使用ApacheHttpClient代替默认client方式

    请根据以下步骤进行操作。 1. 添加依赖 在pom.xml文件的dependencies标签中添加以下依赖: <dependency> <groupId>org.springframework.cloud</groupId> <artifactId>spring-cloud-starter-openfeign&…

    Java 2023年5月19日
    00
  • 只需两步实现Eclipse+Maven快速构建第一个Spring Boot项目

    我会详细讲解“只需两步实现Eclipse+Maven快速构建第一个Spring Boot项目”的完整攻略,过程中会包含两条示例,供大家参考。 1. 新建Maven工程 打开Eclipse,选择File -> New -> Maven Project 在弹出的窗口中,选择archetype,并在Search框中输入“spring-boot”,选择最…

    Java 2023年5月19日
    00
  • Java SpringMVC自学自讲

    以下是关于“Java SpringMVC自学自讲”的完整攻略,其中包含两个示例。 1. 前言 SpringMVC是一种常用的Java Web开发框架,它可以帮助开发者快速构建Web应用程序。本攻略将详细讲解Java SpringMVC的自学自讲方法,帮助读者更好地掌握SpringMVC框架的使用方法。 2. 自学方法 以下是Java SpringMVC的自学…

    Java 2023年5月16日
    00
  • 解决IDEA中编辑HTML格式文件不自动缩进问题

    当在idea中编辑html文件时,有些用户可能会遇到代码不自动缩进的问题,下面介绍两种解决方法: 方法一:开启自动缩进 在IntelliJ IDEA的设置中开启“自动缩进”选项,即可解决问题。 具体步骤: 点击菜单栏中的“File”(文件)-“Settings”(设置)选项,或者使用快捷键“Ctrl+Alt+S”。 在弹出的设置窗口中,在左侧栏中选择“Edi…

    Java 2023年6月15日
    00
  • Spring超详细讲解事务

    Spring超详细讲解事务 什么是事务 事务是指一个操作序列,该操作序列中的所有操作都必须全部执行成功或全部执行失败。事务支持保证数据库的一致性、完整性和隔离性。 Spring事务的优点 在使用Spring进行数据库操作时,使用Spring事务能够带来以下优点: Spring事务对所有的数据库访问代码提供了一致的编程模型 Spring事务可以将数据库事务的边…

    Java 2023年5月19日
    00
  • 你应该知道的21个Java核心技术

    你应该知道的21个Java核心技术攻略 Java作为一门广泛应用于企业级系统开发的编程语言,核心技术对于开发人员非常重要。在这里,我们总结了21个Java核心技术,并提供了相应的攻略,供您参考。 1. Java基础语法 Java基础语法是Java编程的基础,掌握了这些知识,可以轻松地进入Java编程的世界。在学习Java基础语法时,我们应该注重掌握Java数…

    Java 2023年5月23日
    00
  • 如何实现Java的ArrayList经典实体类

    要实现Java的ArrayList经典实体类,我们需要完成以下步骤: 创建实体类:首先需要创建Java类作为实体类,用来描述我们希望在ArrayList中存储的数据结构。例如,我们创建一个书籍类Book,包括属性ISBN、书名、作者和价格。 public class Book { private String isbn; private String nam…

    Java 2023年5月26日
    00
合作推广
合作推广
分享本页
返回顶部