Java HashMap 的 get 方法平均时间复杂度接近 O(1)，通过哈希定位桶+局部结构精确匹配实现；先扰动哈希再位运算索引，桶内依链表或红黑树查找，树化与退化机制保障最坏 O(log n)，且依赖 key 正确实现 hashCode/equals。
Java HashMap 的 get 方法能实现接近 O(1) 的平均查找效率，关键在于它把“定位”和“比对”两个动作做了极致分离：先用哈希快速跳到桶，再在局部结构里精确匹配。
哈希计算与桶定位是第一步
调用 get(key) 时，HashMap 首先对 key 做两次处理：
- 若 key 为
null，直接固定查数组下标 0 的位置； - 否则调用
key.hashCode()得到原始哈希值，再执行扰动函数：(h = key.hashCode()) ^ (h >>> 16)，让高位也参与运算，减少低位重复导致的哈希碰撞； - 用位运算
(n - 1) & hash计算桶索引（n 是数组长度，始终为 2 的幂），比取模%更快且分布更均匀。
桶内查找分三种情况处理
定位到具体桶后，根据该位置的实际结构采取不同策略：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
- 如果桶为空（
null），直接返回null； - 如果桶首节点的 hash 和 key 都匹配（通过
equals()判定），立即返回其 value； - 如果不匹配，则按当前结构继续查找：
- 是链表：从头开始遍历，逐个比对 key 的 hash 和 equals，找到即返回；
- 是红黑树：调用
TreeNode.find()，走红黑树的二叉搜索路径，时间复杂度 O(log n)；
红黑树优化大幅缓解最坏场景
当大量 key 发生哈希冲突、挤进同一个桶时，链表会变长，查找退化为 O(n)。JDK 1.8 引入的树化机制有效抑制了这种退化：
立即学习“Java免费学习笔记（深入）”；
- 仅当链表长度 ≥ 8 且 数组长度 ≥ 64 时，才触发链表转红黑树；
- 树化后，即使上千个 key 冲突到同一桶，查找也稳定在 O(log n)，不会线性变慢；
- 当树中节点数 ≤ 6 时，还会自动退化回链表，节省内存开销。
几个容易被忽略但影响性能的细节
高效不只是靠结构，还依赖 key 的合理设计：
-
重写
hashCode()和equals()必须保持一致：相等的 key 必须有相同哈希值，否则get永远找不到； -
避免 key 频繁修改：一旦 key 的字段参与了
hashCode()计算，后续修改会导致哈希值变化，get就无法正确定位； - null key 虽然支持，但只允许一个：它被硬编码放在下标 0，不经过哈希计算，适合做默认兜底，但不宜滥用。
