containsKey平均O(1)因哈希表通过hashCode快速定位桶，而containsValue需遍历所有entry比较value故为O(n)；TreeMap中二者分别为O(log n)和O(n)。
Map 接口的 containsKey 通常为 O(1)，而 containsValue 一般是 O(n)，根本原因在于底层数据结构的设计目标和实现方式不同。
containsKey 为什么快（平均 O(1)）
HashMap、LinkedHashMap 等主流实现基于哈希表，containsKey 通过 key 的 hashCode() 快速定位到对应桶（bucket），再在该桶的链表或红黑树中查找——平均只需常数次比较。
- 前提是哈希函数分布均匀、负载因子合理（默认 0.75），避免大量哈希冲突
- TreeMap 是例外：它基于红黑树，
containsKey时间复杂度为 O(log n)
containsValue 为什么慢（O(n)）
哈希表本身不建立“值 → 键/位置”的索引。要判断某个 value 是否存在，必须遍历所有 entry，逐一调用 equals() 比较 value 对象。
- 即使 value 是基本类型包装类（如 Integer），也需逐个解包并比较
- 无法跳过任何元素——哪怕第一个 entry 就匹配，最坏仍可能查到最后一个
- TreeMap 同样要遍历全部节点，因为值不参与树的排序逻辑
实际开发中的替代思路
如果频繁按 value 查找，说明当前 Map 设计可能不合理。可考虑：
立即学习“Java免费学习笔记（深入）”；
- 反向 Map：维护一个
Value → Key映射（注意 value 唯一性） - 使用 Guava 的
BiMap，支持双向查找，inverse().get(value)也是 O(1) - 对 value 做缓存或预处理（如将常用 value 提前存入 Set）
别被“平均 O(1)”误导
极端情况下 containsKey 也可能退化为 O(n)：
- 所有 key 哈希值相同（如自定义 key 的
hashCode()总返回 1） - 大量键值对导致频繁扩容，但扩容本身不影响单次查找的摊还复杂度
- Java 8+ 中单个桶超过阈值（TREEIFY_THRESHOLD=8）会转为红黑树，查找变为 O(log k)，k 是桶内元素数
不复杂但容易忽略：时间复杂度是理论保证，实际性能还取决于对象 equals/hashCode 实现质量、JVM 优化、数据规模等。写代码时，优先用 key 查，慎用 value 查。
