当对象 Hashcode 更改时，Hashmap 或 Hashset 中的查找会发生什么 [英] What happens to the lookup in a Hashmap or Hashset when the objects Hashcode changes

问题描述

在 Hashmap 中，提供的键的哈希码用于将值放置在哈希表中.在哈希集中，对象哈希码用于将值放置在底层哈希表中.也就是说，hashmap 的优点是你可以灵活地决定你想要什么作为 key，这样你就可以做这样的好事.

In a Hashmap the hash code of the key provided is used to place the value in the hashtable. In a Hashset the obects hashcode is used to place the value in the underlying hashtable. i.e the advantage of the hashmap is that you have the flexibility of deciding what you want as the key so you can do nice things like this.

Map<String,Player> players = new HashMap<String,Player>();

这可以将诸如玩家姓名之类的字符串映射到玩家本身.

This can map a string such as the players name to a player itself.

我的问题是，当键的 Hashcode 发生变化时，查找会发生什么变化.

My question is is what happens to to the lookup when the key's Hashcode changes.

我希望这对于 Hashmap 来说不是一个主要问题，因为我不希望也不希望密钥改变.在前面的例子中，如果球员的名字改变了，他就不再是那个球员了.但是，我可以使用键更改其他不是名称的字段来查找玩家，并且将来的查找将起作用.

This i expect isn't such a major concern for a Hashmap as I wouldn't expect nor want the key to change. In the previous example if the players name changes he is no longer that player. However I can look a player up using the key change other fields that aren't the name and future lookups will work.

但是在 Hashset 中，因为如果有人稍微更改对象，则使用整个对象的哈希码来放置项目，该对象的未来查找将不再解析到 Hashtable 中的相同位置，因为它依赖于整个对象的哈希码.这是否意味着一旦数据在 Hashset 中就不应更改.还是需要重新散列?还是自动完成等?这是怎么回事?

However in a Hashset since the entire object's hashcode is used to place the item if someone slightly changes an object future lookups of that object will no longer resolve to the same position in the Hashtable since it relies on the entire objects Hashcode. Does this mean that once data is in a Hashset it shouldnt be changed. Or does it need to be rehashed? or is it done automatically etc? What is going on?

推荐答案

在您的示例中，String 是不可变的，因此其哈希码无法更改.但是假设，如果对象的哈希码在哈希表中作为键时确实发生了变化，那么就哈希表查找而言，它可能会消失.我在对相关问题的回答中更详细地介绍了:https://stackoverflow.com/a/13114376/139985.(最初的问题是关于 HashSet，但 HashSet 实际上是一个 HashMap，所以答案也涵盖了这种情况.)

In your example, a String is immutable so its hashcode cannot change. But hypothetically, if the hashcode of an object did change while was a key in a hash table, then it would probably disappear as far as hashtable lookups were concerned. I went into more detail in this Answer to a related question: https://stackoverflow.com/a/13114376/139985 . (The original question is about a HashSet, but a HashSet is really a HashMap under the covers, so the answer covers this case too.)

可以肯定地说，如果 HashMap 或 TreeMap 的键发生变异，会影响它们各自的 hashcode()/equals(Object)或 compare(...) 或 compareTo(...) 合约，则数据结构将中断".

It is safe to say that if the keys of either a HashMap or a TreeMap are mutated in a way that affects their respective hashcode() / equals(Object) or compare(...) or compareTo(...) contracts, then the data structure will "break".

这是否意味着一旦数据在 Hashset 中就不应更改.

Does this mean that once data is in a Hashset it shouldn't be changed.

是的.

还是需要重新散列?还是自动完成等?

Or does it need to be rehashed? or is it done automatically etc?

它不会自动重新散列.HashMap 不会注意到键的哈希码已更改.事实上，当 HashMap 调整大小时，您甚至不会重新计算哈希码.数据结构记住原始哈希码值，以避免在哈希表调整大小时重新计算所有哈希码.

It won't be automatically rehashed. The HashMap won't notice that the hashcode of a key has changed. Indeed, you won't even get recomputation of the hashcode when the HashMap resizes. The data structure remembers the original hashcode value to avoid having to recalculate all of the hashcodes when the hash table resizes.

如果您知道某个键的哈希码将要更改，则需要在更改该键之前从表中删除该条目，然后再将其添加回来.(如果你在改变密钥后尝试 remove/put 它，remove 可能会找不到条目.)

If you know that the hashcode of a key is going to change you need to remove the entry from the table BEFORE you mutate the key, and add it back afterwards. (If you try to remove / put it after mutating the key, the chances are that the remove will fail to find the entry.)

发生了什么事?

发生的事情是您违反了合同.不要那样做！

What is going on is that you violated the contract. Don't do that!

合同由两部分组成:

1. javadoc for Object.

当对象的哈希码是哈希表中的键时，它不能更改的附加约束.

An additional constraint that an object's hashcode must not change while it is a key in a hash table.

HashMap javadoc，但 javadoc for Map 说:

The latter constraint is not stated specifically in the HashMap javadoc, but the javadoc for Map says this:

注意:如果将可变对象用作映射键，则必须非常小心.如果对象的值以影响 equals 比较的方式更改，而对象是映射中的键，则不会指定映射的行为.

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.

影响相等性的更改(通常)也会影响哈希码.在实现级别，如果 HashMap 条目的键的哈希码发生更改，则该条目通常现在位于错误的哈希桶中，并且对 HashMap 执行查找的方法.

A change that affects equality (typically) also affects the hashcode. At the implementation level, if a HashMap entry's key's hashcode changes, the entry will typically now be in the wrong hash bucket and will be invisible to HashMap methods that perform lookups.

这篇关于当对象 Hashcode 更改时，Hashmap 或 Hashset 中的查找会发生什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！