java - 为什么更改用作 HashMap 中键的对象的哈希码会使查找返回 null？

Question

考虑以下场景:

Object o1 = new Object();
Object o2 = new Object();

HashMap<Object, Object> map = new HashMap<Object, Object>();
map.put(o1, o2);

boolean test1 = map.get(o1) == o2; // This evaluates to true

// Now lets say we alter the state of o1:
o1.setSomeInternalState(Object newState);

boolean test2 = map.get(o1) == o2; // This evaluates to false, because now map.get(o1) returns null

假设 o1 的类已覆盖 equals()和 hashCode() .

我在调试过程中遇到了这个问题，因为我已经明确地覆盖了 equals和 hashCode在我在某些业务逻辑中使用的一个特定对象上。我完全理解为什么当我改变对象的状态时对象的哈希码会发生变化，但是为什么 map.get(o1) 会因为它而返回 null？只有一个对象，所以 key 的哈希码不应该匹配吗？

Answer 1

HashMap类通过运行 hashCode 将键映射到值 key 通过哈希函数。散列函数用于创建存储桶数组的索引。例如，一个非常原始的哈希函数是 hashCode % tableSize .更改 key 的 hashCode会改变散列函数创建的索引，这意味着在那个桶中找不到任何东西。

让我们运行一个例子，假设初始 hashCode是 15，表大小是 4:

                         ┌----------------------┐
15 (initial hashCode) -> | hashCode % tableSize | -> index 3
                         |    (hash function)   |
                         └----------------------┘

所以让我们在索引 3 处插入值:

  ┌------┐
0 | null |
  |------|
1 | null |
  |------|
2 | null |
  |------|
3 | key! | <- insert
  └------┘

现在让我们修改 key 的 hashCode所以现在是 13:

                          ┌----------------------┐
13 (modified hashCode) -> | hashCode % tableSize | -> index 1
                          |    (hash function)   |
                          └----------------------┘

索引 1 是什么？没什么，null .

这里简化了很多事情。在真正的哈希表实现中，哈希函数要复杂得多才能创建更均匀的分布。此外，存储桶是链表，因此可以处理冲突。