問(wèn)題描述
在 Hashmap 中,提供的鍵的哈希碼用于將值放置在哈希表中.在哈希集中,對(duì)象哈希碼用于將值放置在底層哈希表中.也就是說(shuō),hashmap 的優(yōu)點(diǎn)是你可以靈活地決定你想要什么作為 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.
我的問(wèn)題是,當(dāng)鍵的 Hashcode 發(fā)生變化時(shí),查找會(huì)發(fā)生什么變化.
My question is is what happens to to the lookup when the key's Hashcode changes.
我希望這對(duì)于 Hashmap 來(lái)說(shuō)不是一個(gè)主要問(wèn)題,因?yàn)槲也幌M膊幌M荑€改變.在前面的例子中,如果球員的名字改變了,他就不再是那個(gè)球員了.但是,我可以使用鍵更改其他不是名稱的字段來(lái)查找玩家,并且將來(lái)的查找將起作用.
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 中,因?yàn)槿绻腥松晕⒏膶?duì)象,則使用整個(gè)對(duì)象的哈希碼來(lái)放置項(xiàng)目,該對(duì)象的未來(lái)查找將不再解析到 Hashtable 中的相同位置,因?yàn)樗蕾囉谡麄€(gè)對(duì)象的哈希碼.這是否意味著一旦數(shù)據(jù)在 Hashset 中就不應(yīng)更改.還是需要重新散列?還是自動(dòng)完成等?這是怎么回事?
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 是不可變的,因此其哈希碼無(wú)法更改.但是假設(shè),如果對(duì)象的哈希碼在哈希表中作為鍵時(shí)確實(shí)發(fā)生了變化,那么就哈希表查找而言,它可能會(huì)消失.我在對(duì)相關(guān)問(wèn)題的回答中更詳細(xì)地介紹了:https://stackoverflow.com/a/13114376/139985.(最初的問(wèn)題是關(guān)于 HashSet
,但 HashSet
實(shí)際上是一個(gè) 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.)
可以肯定地說(shuō),如果 HashMap 或 TreeMap 的鍵發(fā)生變異,會(huì)影響它們各自的 hashcode()
/equals(Object)
或 compare(...)
或 compareTo(...)
合約,則數(shù)據(jù)結(jié)構(gòu)將中斷".
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".
這是否意味著一旦數(shù)據(jù)在 Hashset 中就不應(yīng)更改.
Does this mean that once data is in a Hashset it shouldn't be changed.
是的.
還是需要重新散列?還是自動(dòng)完成等?
Or does it need to be rehashed? or is it done automatically etc?
它不會(huì)自動(dòng)重新散列.HashMap
不會(huì)注意到鍵的哈希碼已更改.事實(shí)上,當(dāng) HashMap
調(diào)整大小時(shí),您甚至不會(huì)重新計(jì)算哈希碼.數(shù)據(jù)結(jié)構(gòu)記住原始哈希碼值,以避免在哈希表調(diào)整大小時(shí)重新計(jì)算所有哈希碼.
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.
如果您知道某個(gè)鍵的哈希碼將要更改,則需要在更改該鍵之前從表中刪除該條目,然后再將其添加回來(lái).(如果你在改變密鑰后嘗試 remove
/put
它,remove
可能會(huì)找不到條目.)
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.)
發(fā)生了什么事?
發(fā)生的事情是您違反了合同.不要那樣做!
What is going on is that you violated the contract. Don't do that!
合同由兩部分組成:
javadoc for
Object
.
當(dāng)對(duì)象的哈希碼是哈希表中的鍵時(shí),它不能更改的附加約束.
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
說(shuō):
The latter constraint is not stated specifically in the HashMap
javadoc, but the javadoc for Map
says this:
注意:如果將可變對(duì)象用作映射鍵,則必須非常小心.如果對(duì)象的值以影響 equals
比較的方式更改,而對(duì)象是映射中的鍵,則不會(huì)指定映射的行為.
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.
影響相等性的更改(通常)也會(huì)影響哈希碼.在實(shí)現(xiàn)級(jí)別,如果 HashMap
條目的鍵的哈希碼發(fā)生更改,則該條目通常現(xiàn)在位于錯(cuò)誤的哈希桶中,并且對(duì) HashMap
執(zhí)行查找的方法.
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.
這篇關(guān)于當(dāng)對(duì)象 Hashcode 更改時(shí),Hashmap 或 Hashset 中的查找會(huì)發(fā)生什么的文章就介紹到這了,希望我們推薦的答案對(duì)大家有所幫助,也希望大家多多支持html5模板網(wǎng)!