HashMap 为什么会查不到？从键的契约到扩容机制

同一个对象明明已经放进 HashMap，get 却返回 null；两个键发生冲突，又为什么不会直接覆盖？这两种现象指向不同层次：对象先决定怎样相等，集合再决定到哪里寻找。本文把键的契约与存储过程串起来，避免把 hashCode、数组下标和业务编号混为一谈。

1. 先定义什么叫同一个键

查询结果首先取决于对象契约。键是否可变，往往比容量大小更先影响正确性。

== 与 equals：问的是不同的问题

对基本类型，== 用于比较值；对对象引用，== 判断是否指向同一个对象。

Object a = new Object();
Object b = new Object();
Object c = a;

System.out.println(a == b); // false
System.out.println(a == c); // true

a 和 b 分别指向两个实例；c 只是拿到了 a 中保存的同一个引用，没有创建新对象。

equals 是方法，它能让一个类定义自己的相等规则。没有重写时，Object.equals 采用引用相等；重写后，可以按编号、文本等内容比较。Object.equals 官方说明

因此，不能直接记成“== 比地址，equals 比内容”。更准确的说法是：

如果一个类没有重写 equals，两个字段完全相同的实例也未必被认为相等。

hashCode 为什么要和 equals 配合？

hashCode() 返回一个 int，哈希集合可以利用它缩小查找范围。它不是唯一编号，也不能用来判断对象一定相等。

最重要的约定是：如果两个对象根据 equals 相等，它们必须返回相同的哈希值；哈希值相同，则不一定相等。 相等比较所依赖的信息没有变化时，哈希值也应保持稳定。Object.hashCode 官方约定

可以这样理解两者的分工：

哈希计算：缩小查找范围
equals：在候选对象中确认逻辑相等

为什么不同对象可以有同一个哈希值？因为哈希值的范围有限，不可能给任意多的不同对象都分配一个不同的 int。这种情况叫哈希冲突。

冲突本身是正常现象，集合需要能够区分这些对象。

业务中怎样设计可靠的键？

优先使用稳定的标识

如果业务只是按照用户编号查询，直接使用编号就足够：

Map<Long, String> namesByUserId = new HashMap<>();
namesByUserId.put(1L, "Alice");

用户可以修改名字，但这不会改变 Map 中作为键的用户编号。

不过，生成型数据库主键尚未分配时，不应该把依赖该主键的实体直接放进哈希集合，之后再修改主键。键的稳定性应从实际生命周期考虑。

需要组合键时，使用专门的键类型

假设业务按租户编号和用户编号共同识别一个用户，可以使用 Java 17 的 record：

record TenantUserKey(long tenantId, long userId) {}

Map<TenantUserKey, String> map = new HashMap<>();
map.put(new TenantUserKey(10L, 1L), "Alice");

System.out.println(map.get(new TenantUserKey(10L, 1L))); // Alice

record 会基于组件提供相等与哈希方法。这里组件都是基本类型，适合作为稳定键。Record 官方说明

但 record 不代表深度不可变。如果组件是可变 List，修改列表仍可能影响基于它计算的相等性和哈希值。final 引用也不能阻止被引用对象发生变化。

确实要改变键时，先移除，再使用新键插入

正确顺序是：在旧键仍能正常匹配时移除它，然后构造新键并插入。

UserKey oldKey = new UserKey(1L);
UserKey newKey = new UserKey(2L);

Map<UserKey, String> map = new HashMap<>();
map.put(oldKey, "Alice");

String value = map.remove(oldKey);
map.put(newKey, value);

这个演示假设旧映射存在、新键没有冲突。真实业务需要判断这些条件；如果支持 null 值，也不能单靠返回值为 null 判断原映射是否存在。

并发情况下，移除再插入也不是一个天然原子的操作，需要另外设计同步或业务约束。换成 ConcurrentHashMap 并不能自动修复可变键问题。

2. 沿着 put 找到真正的分支

用一次插入把哈希、桶定位和覆盖判定连接起来。源码说明限定为 OpenJDK 17。

HashMap 存放的不是一堆孤立的键和值

HashMap 内部有一个数组，可以把它理解为按下标排列的一组存储入口。每个入口叫一个桶。

数组下标       桶中的节点

0             空
1             [keyA, valueA] → [keyB, valueB]
2             [keyC, valueC]
3             空
...
15            空

一个节点保存键、值、计算后的哈希信息，以及与其他节点连接所需要的信息。多个键定位到同一个桶时，不会直接互相覆盖，它们可以通过链表连接；达到特定条件时，桶内结构也可以转换为红黑树。

先区分两个容易混淆的量：

容量为 16，不代表只能存 16 个映射。一个桶可以容纳多个节点。不过随着映射增多，冲突和查找成本可能增加，因此 HashMap 会在适当的时候扩容。

第一步：计算用于定位的哈希值

非空键首先提供自己的 hashCode()，HashMap 再对结果做一次位运算：

int original = key.hashCode();
int hash = original ^ (original >>> 16);

>>> 是无符号右移，左侧空出来的位补零；^ 是按位异或，对应位不同则为 1，相同则为 0。

为什么不直接使用原始哈希值？

因为下一步计算数组位置时，主要使用低位。如果两个哈希值只在高位不同，低位却完全一样，在小数组中就容易落到同一个位置。

假设两个原始值分别是：

0x00000001
0x00010001

它们的低 16 位都是 1。混入高位以后：

0x00000001 ^ 0x00000000 = 0x00000001
0x00010001 ^ 0x00000001 = 0x00010000

低位也产生了差异。这种处理有助于改善部分哈希分布，但无法消除所有冲突。

对于 null 键，HashMap 使用哈希值 0。这也是它能够接收 null 键的实现基础之一。

第二步：把哈希值转换为数组下标

对于长度为 n 的数组，定位形式为：

int index = (n - 1) & hash;

& 是按位与，只有对应的两位都为 1，结果才是 1。

如果数组长度是 16，那么 n - 1 就是 15，二进制低位为：

15 = 0000 1111

它与哈希值做按位与，效果就是取哈希值的低 4 位，得到 0～15 的下标。

下面三个值都落在下标 1：

这里有一个区别：落在同一个桶，不代表完整哈希值相同。

示例中的哈希值分别为 1、17、33，只是当前数组太短，定位时使用的低位恰好相同。

为什么数组长度是 2 的幂？

当数组长度是 2^k，n - 1 的低 k 位恰好全部为 1，可以直接用掩码取出低位。

例如：

容量 16：掩码 15，低 4 位全为 1
容量 32：掩码 31，低 5 位全为 1
容量 64：掩码 63，低 6 位全为 1

假设仍然使用这个公式，却把容量设置为 10，掩码 9 的二进制是 1001。某些位被固定清零，不是所有 0～9 的位置都能被充分使用。

这不是说哈希表只能使用 2 的幂。其他哈希表可以采用不同的容量和定位方案；这是理解当前 HashMap 实现时需要掌握的设计配合。

在 OpenJDK 17 中，传入 new HashMap<>(20) 这样的初始容量，内部会把目标数组长度调整为不小于它的 2 的幂，也就是 32。但数组通常要到首次插入时才分配。

第三步：判断新增，还是更新

定位到桶以后，可以先按四种情况理解 put：

桶为空：直接插入

插入前：桶 1 → 空
插入后：桶 1 → [keyA, valueA]

新建节点，增加映射数量。

找到相等的键：更新值

例如：

Map<String, String> map = new HashMap<>();
map.put("name", "Alice");
String previous = map.put("name", "Bob");

System.out.println(previous);        // Alice
System.out.println(map.get("name")); // Bob
System.out.println(map.size());      // 1

第二次插入更新已有映射，size 不增加，put 返回旧值。

如果是新增映射，put 返回 null。不过已有映射的旧值也可能是 null，所以不能仅凭返回 null 判断之前不存在这个键。需要判断存在性时，可以使用 containsKey。HashMap 的 put 方法说明

桶是链表：逐个比较

假设已经有两个节点：

桶 1 → [keyA] → [keyB]

插入 keyC 时，如果它与已有键都不相等，就会新增节点：

桶 1 → [keyA] → [keyB] → [keyC]

比较键时，需要先匹配保存的哈希信息，再检查引用相同或 equals 相等。

这与前面键契约的结论相连：如果相等键的哈希规则不一致，或者插入后修改了相关字段，查找和更新都可能出现问题。

桶已经是树：按树节点逻辑处理

如果桶已转换为红黑树，就走对应的查找和插入路径。红黑树是一种保持平衡的搜索树，目的是限制树的高度。

不过不能只看见红黑树，就断言任何键的查询都一定是 O(log n)。当大量键具有相同哈希值，并且无法通过合适的比较顺序区分时，查找仍可能需要搜索多个分支。

合理设计哈希分布，仍然比依赖树化兜底更重要。

把 put 的主要过程串起来

下面是帮助理解的伪代码，不是可直接运行的源码：

计算键的哈希信息

如果数组还没分配：
    分配数组

计算桶下标

如果桶为空：
    创建节点
否则：
    查找已有的相等键
    如果找到：
        更新值，返回旧值
    如果没找到：
        按链表或树的规则插入
        必要时判断树化或扩容

增加映射数量
如果超过扩容阈值：
    扩容并重新分布节点

返回 null

源码中可以沿着 put → putVal 阅读；遇到结构变化时，再进入 treeifyBin 或 resize。先用这些方法建立路径，再逐步看具体分支，比一开始阅读全部代码更容易。OpenJDK 17u HashMap 源码

3. 扩容与树化各自解决什么

扩容改变桶数量，树化改变一个桶内的组织方式，两者不能用一个阈值概括。

默认容量 16，为什么第 13 个映射可能触发扩容？

这里还有两个量：负载因子和扩容阈值。

负载因子用于表达空间占用与冲突成本的取舍，默认值是 0.75。普通容量下，阈值可以理解为：

threshold = capacity × loadFactor

默认数组分配为 16 个桶时：

threshold = 16 × 0.75 = 12

新增映射后，size 超过这个阈值，就触发基于数量的扩容：

因此是“超过阈值”，不是“达到阈值”。另外，更新已有键只替换值，不会因为 size 增加而触发这条路径。

在普通的倍增过程中，容量从 16 变为 32，阈值相应从 12 变为 24。

但不要把“第 13 个才扩容”理解为所有情况的结论：桶内冲突过多时，也可能通过另一条路径提前扩容；自定义初始容量或负载因子也会改变结果。HashMap 容量与负载因子说明

扩容以后，节点怎样移动？

扩容不是把旧数组原样复制进新数组。数组长度变化了，定位掩码也变了，一些节点需要移动。

继续看之前的哈希值 1、17、33。旧容量为 16，三个节点都在桶 1。新容量为 32，掩码变为 31：

因此原来的链表可以拆成两组：

扩容前：
桶 1  → 1 → 17 → 33

扩容后：
桶 1  → 1 → 33
桶 17 → 17

为什么只有两个去向？

因为容量翻倍后，掩码只增加了一个有效位。新增的这一位如果是 0，节点留在原下标；如果是 1，节点移动到“原下标 + 旧容量”。

这个例子里，新增位对应数值 16：

1  & 16 = 0  → 留在 1
17 & 16 = 16 → 移到 1 + 16 = 17
33 & 16 = 0  → 留在 1

扩容迁移利用节点保存的哈希信息，不需要重新调用每个键的 hashCode()。但创建更大的数组、遍历和连接节点仍然有成本，不能把扩容视为免费的操作。

链表什么时候会变成红黑树？

OpenJDK 17 中，树化相关的两个重要阈值是：

判断逻辑同时关注桶内节点数量和数组长度。

如果数组还比较小，冲突过多时优先扩容，希望新增的有效位能把节点分散到不同桶。数组足够大以后，继续发生集中冲突，才考虑转成树。

还有一个细节：常量等于 8，不意味着插入第 8 个节点就立刻树化。

沿本文讨论的 putVal 链表追加路径，当桶已有 8 个节点，再新增第 9 个不相等的键时，会进入相关判断；是否真正树化，还要看数组容量。

例如预设容量为 64，并让多个不同键的哈希值都为 1：

放入前 8 个不同键：桶内仍是链表
追加第 9 个不同键：进入树化，容量条件也已满足

如果从默认容量开始，相同的冲突序列可能先导致数组扩容，所以不能忽略前提。

退化为链表也不能简单概括成“少于 6 就一定退化”。阈值 6 会参与扩容时的树桶拆分判断，而删除路径还会考虑树的形态。

初始容量怎样设置？

假设预计保存 100 个不同键。如果直接设置：

new HashMap<>(100);

OpenJDK 17 首次分配的数组长度是 128。默认负载因子下，阈值为 96，插入到第 97 个映射时就会超过数量阈值。

如果希望为这 100 个映射预留足够空间，可以先按映射数量和负载因子估算：

100 ÷ 0.75 ≈ 133.33
向上取整为 134
内部目标数组长度再调整为 256

不过这也意味着更多的空桶和内存占用。预设容量要根据实际规模选择，不能一味设置得很大。

另外，这个估算主要避免基于映射数量的扩容，不保证消除其他冲突问题。容量不是修复错误哈希规则的办法。

HashMap 的“无序”和线程安全问题

HashMap 不保证按插入顺序遍历。某次输出看起来有顺序，可能只是当前键和数组结构带来的结果；换一组键、发生扩容或换一个实现后，都不能继续依赖这个观察。

需要维护插入顺序时，可以考虑 LinkedHashMap；需要基于键排序时，可以考虑 TreeMap，并明确比较规则。

HashMap 也不提供并发同步保证。多个线程并发访问并修改共享 Map，需要使用合适的同步机制或并发集合。不能因为一次并发测试“没有出错”，就认为它安全。HashMap 的遍历与并发说明

树化解决的是特定冲突场景的结构问题，不会让 HashMap 自动获得线程安全。

4. 设计判断与适用边界

业务键优先采用稳定标识或不可变值对象。把昵称、状态和更新时间放进相等规则，会让业务更新改变查询位置。使用缓存或去重集合时，先写出哪些字段决定身份，再让 equals 与 hashCode 使用一致的信息。

容量优化建立在正确性之后。预计映射数量、负载因子和实际键分布共同影响容量选择；把树化阈值背成一句口号，无法解释容量较小时为什么先扩容。若涉及多线程更新，则转到并发容器和原子组合操作，不能依赖 HashMap 内部结构消除数据竞争。

5. 问答

问：为什么重写 equals 时通常也要重写 hashCode？

因为哈希集合先用哈希信息缩小查找范围，再判断键是否相等。如果相等对象产生不同哈希值，就无法保证通过等价键找到已有映射。

问：hashCode 相同，两个对象就相等吗？

不能。哈希冲突是正常现象，最终还要根据相等规则区分。示例中的 "Aa" 和 "BB" 就是反例。

问：HashMap 的 put 做了什么？

计算哈希，按数组长度定位桶；空桶直接插入，非空桶查找相等键。找到则更新值，否则按链表或树的逻辑新增；新增后检查数量阈值，并在相关条件下扩容或调整桶内结构。

问：为什么使用高位与低位异或？

小容量数组定位时主要使用低位，混入高位有助于让高位差异参与定位，改善部分分布。

参考资料

• Java 17 Object：equals 与 hashCode
• Java 17 Map：键相等性与可变键说明
• Java 17 HashMap API
• OpenJDK 17u HashMap 源码
• Java 17 Record API
• Java 17 LinkedHashMap API
• Java 17 TreeMap API