为什么在HashMap中改变用作键的对象的哈希码会使查找返回null？ [英] Why does changing the hashcode of an object used as a key in a HashMap make a lookup return null?

问题描述

考虑以下情形：

  Object o1 = new Object（）; 
 Object o2 = new Object（）; 
 
 HashMap< Object，Object> map = new HashMap< Object，Object>（）; 
 map.put（o1，o2）; 
 
布尔test1 = map.get（o1）== o2; //计算结果为真
 
 //现在让我们说改变o1的状态：
 o1.setSomeInternalState（Object newState）; 
 
布尔test2 = map.get（o1）== o2; //因为现在map.get（o1）返回null 
  

假设类的值为false，对于o1已重写 equals（）和 hashCode（）。

我在调试过程中遇到过这个问题，因为我已经在一个特定的对象I上明确地重写了 equals 和 hashCode 在某些商业逻辑中使用。我可以完全理解为什么当我改变它的状态时对象的哈希码发生了变化，但为什么map.get（o1）因为它而返回null？只有一个对象，所以密钥的哈希码不匹配？

解决方案

HashMap

code> class通过散列函数运行密钥的 hashCode 来将键映射到值。哈希函数用于创建一个索引到一个桶数组中。例如，一个 原始哈希函数将是 hashCode％tableSize 。改变密钥的 hashCode 会改变哈希函数创建的索引，这意味着在该桶中没有任何东西可以找到。

假设最初的 hashCode 是15并且表大小是4：

$ p> ┌----------------------┐
15（initial hashCode） - > | hashCode％tableSize | - >索引3
| （散列函数）|
└----------------------┘


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

 ┌------┐
 0 | null | 
 | ------ | 
 1 | null | 
 | ------ | 
 2 | null | 
 | ------ | 
 3 |键！ | <  -  insert 
└------┘
  

现在让我们修改关键字 hashCode 现在是13：

 ┌---- ------------------┐
 13（修改hashCode） - > | hashCode％tableSize | - >索引1 
 | （散列函数）| 
└----------------------┘
  

索引1处是什么？没有什么， null 。

这里简化了很多东西。在真正的散列表实现中，散列函数要创建更均匀的分布要复杂得多。此外，桶是链表，因此可以处理碰撞。

Consider the following scenario:

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

Assume that the class for o1 has overridden equals() and hashCode().

I've encountered this issue during debugging because I had explicitly overridden equals and hashCode on one particular object I'm using in some business logic. I can fully appreciate why the hashcode of the object changes when I alter its state, but why should the map.get(o1) return null because of it? There is only one object, so shouldn't the key's hashcode match?

解决方案

The HashMap class maps keys to values by running the hashCode of the key through a hash function. The hash function is used to create an index into an array of buckets. For example, a very primitive hash function would be hashCode % tableSize. Changing the key's hashCode would alter the index created by the hash function, meaning there is nothing to be found in that bucket.

Let's run an example, assuming that the initial hashCode is 15 and the table size is 4:

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

So let's insert the value at index 3:

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

Now let's modifiy the key's hashCode so that it is now 13:

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

What's at index 1? Nothing, null.

A lot of things have been simplified here. In a real hash table implementation, the hash function is much more complex to create a more even distribution. Also, the buckets are linked-lists so collisions can be handled.

这篇关于为什么在HashMap中改变用作键的对象的哈希码会使查找返回null？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！