HashMap查找键值对的底层寻址过程是“一次哈希+一次定位+一次比对”:先调用hash()扰动处理key的hashCode((h = key.hashCode()) ^ (h >>> 16)),再用(n-1)&hash位运算快速定位数组下标,最后在桶内通过hash比对和equals()语义匹配确定目标节点,支持链表O(n)或红黑树O(logn)查找,平均时间复杂度为O(1)。

HashMap 查找键值对的底层寻址过程,核心是“一次哈希 + 一次定位 + 一次比对”,整个过程平均耗时接近常数级 O(1)。它不是靠遍历,而是靠数学映射快速锁定位置,但必须处理冲突和结构演进这两个现实问题。
哈希计算与扰动处理
查找开始前,先对 key 调用 hash() 方法(非直接用 hashCode())。这个方法做了高位参与运算的扰动: (h = key.hashCode()) ^ (h >>> 16) 目的是让 hash 值的高、低比特位都参与索引计算,降低低位相同导致的聚集碰撞——尤其当数组容量较小时,仅依赖 hashCode 低几位容易让大量 key 挤在少数桶里。
桶索引快速定位
得到扰动后的 hash 值后,用位运算 (n - 1) & hash 算出数组下标(n 是 table 长度,恒为 2 的幂)。这等价于取模 hash % n,但位运算快得多。 例如:容量为 16(n=16,n−1=15=0b1111),hash=1234(0b10011010010),取低 4 位得 0b0010 = 2 → 定位到 table[2]。
桶内匹配逻辑:从链表到红黑树
定位到桶(table[i])后,分三种情况处理:
- 如果桶为空(tab[i] == null),直接返回 null;
- 如果桶中只有一个节点(p.hash == hash && (k = p.key) == key || key.equals(k)),命中,返回 value;
- 如果桶中是链表或红黑树: → 先比 hash 值,再调用 key.equals() 逐个比对; → 若是 TreeNode 类型,则走红黑树的 log(n) 查找路径; → 注意:即使 hash 相同,也必须用 equals() 确认语义相等,这是 HashMap 支持自定义对象作 key 的基础。
为什么不能只靠 hash 值判断相等
不同对象可能有相同 hash 值(哈希碰撞天然存在),比如 "Aa" 和 "BB" 在 Java 中 hashCode 都是 2112。只比 hash 会误判,所以必须结合 equals() 才能保证语义正确性。这也是为什么重写 equals() 时必须重写 hashCode() ——否则 put 进去的 key,get 时可能找不到。


















