HashMap根据键获取值平均时间复杂度为O(1)，先通过hashCode()和扰动运算定位桶，再用==或equals()比对键；需正确重写hashCode()和equals()，且键应尽量不可变。

HashMap 通过哈希码（hash code）和数组索引直接定位，平均时间复杂度为 O(1)，所以根据键获取值非常快。

哈希计算与桶定位

当你调用 map.get(key) 时，HashMap 先调用 key 的 hashCode() 方法，得到一个整数哈希值；再对该值做扰动运算（高位参与运算），然后与内部数组长度减一做按位与（& (n-1)），快速算出该键应落在哪个“桶”（数组索引位置）。

处理哈希冲突（链表或红黑树）

多个键可能映射到同一个桶，这时 HashMap 用链表或红黑树存储多个节点。它会遍历该桶中的节点，用 == 或 equals() 判断键是否相等：

OpenJDK 24

下载

• 先比较引用（==），相同则直接返回对应 value
• 引用不同则调用 key.equals(e.key)，匹配成功才返回 value
• 如果当前桶是红黑树结构，会走树的查找逻辑（O(log n)，但极少触发）

关键前提：键的正确实现

要保证 get 正确高效，必须满足：

立即学习“Java免费学习笔记（深入）”；

• key 必须正确重写 hashCode() 和 equals()，且两者逻辑一致
• key 在放入后尽量保持不变（尤其不能修改影响 hashCode() 和 equals() 的字段）
• 使用不可变类（如 String、Integer）作 key 最安全

简单示例

以下操作都是常数级平均耗时：

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
Integer count = map.get("apple"); // 直接定位到对应桶，再比对 key，拿到 5