What happens to the lookup in a Hashmap or Hashset when the objects Hashcode changes

Question

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.

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

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.

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?

Answer 1

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.)

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".

---

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

Yes.

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

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.

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?

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

The contract consists of two things:

1. The standard hashcode / equals contract as specified in the javadoc for Object.

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

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

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.

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.