HashMap平均查找为O(1)，关键在于哈希值到数组索引的映射（位运算定位桶）与桶内结构控制（链表≤7时均摊O(1)，红黑树时O(log n)但概率极低）协同作用，前提是哈希均匀、负载因子合理、key正确重写hashCode/equals。
Java 中 HashMap 查找元素的平均时间复杂度是 O(1)，但这不是绝对的常数时间，而是建立在合理使用前提下的摊销（amortized）表现。
哈希计算与桶定位：两步都是 O(1)
查找一个 key 时，实际执行的是三个固定步骤：
- 调用
key.hashCode()得到整型哈希码 —— 时间固定，O(1) - 执行扰动函数（如 JDK8 的
(h = key.hashCode()) ^ (h >>> 16)），改善低位分布 —— 仍为 O(1) - 通过位运算
hash & (table.length - 1)算出数组下标（要求容量是 2 的幂）—— 位运算，O(1)
这三步加起来仍是常数时间，结果直接给出目标桶（数组索引）的地址。
桶内查找：决定“最后一跳”的耗时
定位到桶后，真正的比对发生在该桶挂载的数据结构中：
立即学习“Java免费学习笔记（深入）”；
- 空桶或仅一个节点：直接比对 key，O(1)
- 链表（长度 ≤ 7）：最多遍历几次 equals，均摊仍接近 O(1)
- 红黑树（长度 ≥ 8 且 table.length ≥ 64）：查找为 O(log n)，但 n 是单个桶内元素数，不是全表大小；在负载因子 0.75 下，桶长度 > 8 的概率低于千万分之一
为什么均匀分布能支撑 O(1)？
假设 HashMap 有 n 个元素、初始容量 16、负载因子 0.75：
- 扩容触发点是 n > 12，之后容量翻倍，保证桶数量始终与元素量同阶
- 若哈希值均匀，平均每个桶约含 n / capacity ≈ 0.75 个元素 —— 绝大多数桶为空或仅 1 个节点
- 此时
get()、containsKey()等操作，99% 以上走的是“定位桶 → 比对一次 key”的路径
这就是摊销意义下 O(1) 的实质：不是每次绝对不变，而是在哈希均匀、负载因子合理、key 正确重写 hashCode() 和 equals() 的条件下，平均成本恒定且极低。
哪些情况会让查找退化？
以下情形会显著拉高查找耗时，甚至退化为 O(n)：
- 自定义 key 未重写
hashCode()或equals()：所有对象哈希值相同，全部挤进一个桶 → 链表变长 - 哈希函数质量差或输入恶意聚集（如大量字符串共享前缀）：冲突率上升
- 长期不扩容又高频插入：容量过小，桶密度过高
- 频繁调用
containsValue()：该方法必须遍历所有桶和所有节点 → 固定 O(n)，与哈希无关
