萍乡市网站建设_网站建设公司_内容更新_seo优化

PriorityBlockingQueue<E>是 Java 并发包（java.util.concurrent）中提供的一个线程安全的、无界、优先级队列。它的核心思想是：

每次取出的元素，都是当前队列中“优先级最高”的那个元素（即最小值，依据自然排序或自定义比较器）。

一、关键特性总结

二、核心机制解析

1.底层数据结构：二叉最小堆

• 使用Object[] queue存储元素。
• 对于任意节点i：
  • 左孩子：2*i + 1
  • 右孩子：2*i + 2
  • 父节点：(i - 1) / 2
• 堆性质：父节点 ≤ 子节点→ 根节点（queue[0]）是最小值（最高优先级）。

2.扩容机制（tryGrow）

• 当数组满时，自动扩容：
  • 小容量（<64）：增长较快（+ oldCap + 2）
  • 大容量：增长 50%（oldCap >> 1）
• 特殊设计：扩容时不持有主锁（lock），而是用CAS 自旋锁（allocationSpinLock）避免阻塞消费者。
  • 目的：防止生产者扩容时长时间持有锁，导致消费者“饿死”。

3.堆调整操作

• siftUp：插入新元素后，从底部向上调整（冒泡到合适位置）。
• siftDown：删除根节点后，把最后一个元素放到根，再向下调整。
• 分为两种版本：
  • siftUpComparable/siftDownComparable：使用元素自身的compareTo()
  • siftUpUsingComparator/siftDownUsingComparator：使用外部Comparator

4.构造函数逻辑

• 如果传入的是SortedSet或PriorityQueue，直接复用其排序规则（无需重新建堆）。
• 否则，对传入集合调用heapify()从底向上建堆（时间复杂度 O(n)）。

5.阻塞与非阻塞操作

6.关于迭代器（重要！）

Iterator<E>it=pq.iterator();// ❌ 不保证按优先级顺序遍历！

• 原因：堆的数组存储不是排序数组，只是满足堆性质。
• 正确做法：如需有序遍历，必须：

  Object[]arr=pq.toArray();Arrays.sort(arr);// 或使用 Comparator

三、FIFOEntry 示例：解决“优先级相同时的公平性”

当多个元素优先级相同（compareTo == 0），默认不保证谁先出队。

解决方案：引入“插入顺序”作为第二排序键。

classFIFOEntry<EextendsComparable<?superE>>implementsComparable<FIFOEntry<E>>{staticfinalAtomicLongseq=newAtomicLong(0);finallongseqNum;// 插入序号finalEentry;publicintcompareTo(FIFOEntry<E>other){intres=entry.compareTo(other.entry);if(res==0)res=Long.compare(seqNum,other.seqNum);// 先插入的先出returnres;}}

使用时：pq.offer(new FIFOEntry(myElement));

四、典型使用场景

• 任务调度系统：高优先级任务先执行。
• 事件处理：紧急事件优先处理。
• 合并多个有序流：如多路归并（配合take()阻塞特性）。

五、注意事项

1. 不要依赖iterator()的顺序！
2. 避免在比较器中抛异常：会导致队列状态不一致。
3. 内存风险：虽然是“无界”，但大量积压会导致 OOM。
4. 性能：高并发下，所有操作串行化（单锁），吞吐量不如ConcurrentLinkedQueue，但语义不同。

总结

PriorityBlockingQueue=线程安全的 PriorityQueue + BlockingQueue 接口
它适合需要按优先级消费、且允许多线程协作的场景，但要注意其无界性和迭代无序性。

如果你理解了二叉堆、CAS 自旋锁、以及阻塞条件（Condition notEmpty），就掌握了它的精髓。