PriorityBlockingQueue在java中的原理-java教程-PHP中文网

PriorityBlockingQueue在java中的原理

舞姬之光

发布： 2025-12-18 16:15:07

原创

611人浏览过

PriorityBlockingQueue基于无界最小堆、显式锁和条件等待实现线程安全优先级队列：数组模拟完全二叉树，插入上浮、删除下沉，O(log n)时间复杂度；默认自然序或自定义Comparator；无界扩容（初始11，

priorityblockingqueue在java中的原理

PriorityBlockingQueue 的核心原理是：用**无界二叉堆 + 显式锁 + 条件等待**，实现线程安全的优先级排序与阻塞行为。

基于最小堆的优先级排序

它底层用数组模拟完全二叉树（默认最小堆），保证堆顶元素始终是优先级最高（即最小）的元素。插入时执行“上浮”（sift-up），从末尾开始比较父节点，一路交换直到满足堆序；出队时取走堆顶，用最后一个元素补位，再“下沉”（sift-down）调整位置。整个过程不全排序，只维护父子关系，所以时间复杂度为 O(log n)，远优于每次遍历找最大值。

默认按元素自然顺序（Comparable）排序；也可传入 Comparator 自定义优先级规则
同优先级元素不保证 FIFO 顺序，这是堆结构的固有特性
直接遍历 queue 数组看到的是堆序数组，不是逻辑上的有序序列

无界设计与动态扩容

它初始容量为 11，但没有固定上限——当数组满时会自动扩容。扩容策略是：size 。为避免扩容期间长期持锁影响并发性能，它先释放主锁，用 CAS 控制仅一个线程执行扩容（通过 allocationSpinLock 字段），扩容完再重新加锁复制数据。

写操作（如 offer/put）几乎永不阻塞，只在内存耗尽时抛 OOM
因此不适合写压极高且内存受限的场景，否则可能撑爆堆内存
最大容量为 Integer.MAX_VALUE − 8，是 JVM 层面的硬限制

线程安全与阻塞机制

所有关键操作（offer、poll、take、remove 等）都由一把 ReentrantLock 保护，确保修改 queue 数组和 size 的原子性。消费者调用 take() 时若队列为空，会在 notEmpty 条件变量 上 await；生产者插入成功后立即 signal 唤醒等待线程。注意：它只有 notEmpty，没有 notFull —— 因为写不阻塞。