問題描述

在 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 中的查找會發生什么的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！