Are mutable hashmap keys a dangerous practice?

Question

Is it bad practice to use mutable objects as Hashmap keys? What happens when you try to retrieve a value from a Hashmap using a key that has been modified enough to change its hashcode?

For example, given

class Key {     int a; //mutable field     int b; //mutable field      public int hashcode()         return foo(a, b);     // setters setA and setB omitted for brevity } 

with code

HashMap<Key, Value> map = new HashMap<Key, Value>();  Key key1 = new Key(0, 0); map.put(key1, value1); // value1 is an instance of Value  key1.setA(5); key1.setB(10); 

What happens if we now call map.get(key1)? Is this safe or advisable? Or is the behavior dependent on the language?

Answer 1

It has been noted by many well respected developers such as Brian Goetz and Josh Bloch that :

If an object’s hashCode() value can change based on its state, then we must be careful when using such objects as keys in hash-based collections to ensure that we don’t allow their state to change when they are being used as hash keys. All hash-based collections assume that an object’s hash value does not change while it is in use as a key in the collection. If a key’s hash code were to change while it was in a collection, some unpredictable and confusing consequences could follow. This is usually not a problem in practice — it is not common practice to use a mutable object like a List as a key in a HashMap.

Answer 2

This is not safe or advisable. The value mapped to by key1 can never be retrieved. When doing a retrieval, most hash maps will do something like

Object get(Object key) {     int hash = key.hashCode();     //simplified, ignores hash collisions,     Entry entry = getEntry(hash);     if(entry != null && entry.getKey().equals(key)) {         return entry.getValue();     }     return null; } 

In this example, key1.hashcode() now points to the wrong bucket of the hash table, and you will not be able to retrieve value1 with key1.

If you had done something like,

Key key1 = new Key(0, 0); map.put(key1, value1); key1.setA(5); Key key2 = new Key(0, 0); map.get(key2); 

This will also not retrieve value1, as key1 and key2 are no longer equal, so this check

    if(entry != null && entry.getKey().equals(key))  

will fail.