priorityqueue 的 contains() 方法时间复杂度为 o(n)，因其底层基于无序索引的堆结构，只能线性遍历比较；频繁调用会导致性能退化，推荐配合 hashset 实现 o(1) 查找。
Java 中 PriorityQueue 的 contains() 方法确实会触发线性扫描，时间复杂度为 $O(n)$，这是由其底层实现决定的——它基于堆（heap）结构，而堆本身不维护元素的哈希索引或有序链表，无法支持快速查找。
为什么 contains() 必须遍历？
PriorityQueue 内部使用数组存储的二叉最小堆（或最大堆），只保证“堆序性”（即父节点 ≤ 子节点），不保证整体有序，也不记录元素位置映射。因此，contains(Object o) 只能逐个比较每个元素（调用 equals()），无法跳过任何项。
- 即使堆中已有目标元素，也无法通过堆性质快速定位
- 重复元素可能分布在任意下标，无法剪枝优化
- 没有额外索引结构（如 HashMap）辅助查找
常见误用场景
开发者常在循环中频繁调用 contains() 判断某任务是否已入队，例如：
if (!pq.contains(task)) { pq.offer(task); }
这种写法在队列较大时（比如数千元素）会导致性能明显下降，尤其当插入前都做一次检查时，整体复杂度退化为 $O(n^2)$。
deep-java-review
下载
Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...
更高效的替代方案
若需高频存在性判断，应组合其他数据结构来弥补堆的短板：
-
搭配 HashSet：用
HashSet同步维护元素集合，contains()降为 $O(1)$ 平均复杂度；插入/删除时同步更新两个结构 -
自定义包装类：封装
PriorityQueue+Set，统一管理增删查逻辑，避免外部不同步 -
改用 TreeSet（若允许）：当元素可比较且无需重复、对“优先级+去重+查找”三者有同等需求时，
TreeSet支持 $O(\log n)$ 查找与排序，但不支持重复元素和灵活的优先级策略
注意 remove() 同样是 O(n)
remove(Object o) 在 PriorityQueue 中也是线性扫描 + 堆重构，最坏 $O(n)$。如果需要高效删除任意元素（如延迟任务取消），同样建议用 HashSet 标记逻辑删除，或改用支持双端操作的结构（如 DelayQueue 配合取消标记）。
不复杂但容易忽略：堆擅长高效取极值，不擅长随机查找——用对结构，才能守住性能边界。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
