为什么更改用作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？只有一个对象,所以密钥的哈希码不应该匹配吗？

Answer 1

该HashMap班通过运行键映射到值hashCode通过该键的哈希函数.哈希函数用于创建桶数组的索引.例如,一个非常原始的哈希函数hashCode % tableSize.更改密钥hashCode会改变散列函数创建的索引,这意味着在该存储桶中找不到任何内容.

让我们运行一个例子,假设初始hashCode值为15且表大小为4:

                         ?----------------------?
15 (initial hashCode) -> | hashCode % tableSize | -> index 3
                         |    (hash function)   |
                         ?----------------------?

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

  ?------?
0 | null |
  |------|
1 | null |
  |------|
2 | null |
  |------|
3 | key! | <- insert
  ?------?

现在让我们修改密钥hashCode,使其现在为13:

                          ?----------------------?
13 (modified hashCode) -> | hashCode % tableSize | -> index 1
                          |    (hash function)   |
                          ?----------------------?

索引1是什么？什么都没有null.

这里简化了很多东西.在实际的哈希表实现中,哈希函数要复杂得多,以创建更均匀的分布.此外,存储桶是链接列表,因此可以处理冲突.