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?
If you want to make a mutable object as a key in the hashmap, then you have to make sure that the state change for the key object does not change the hashcode of the object. This can be done by overriding the hashCode() method. But, you must make sure you are honoring the contract with equals() also.
Both hashcode and equals method are used in put and get method of HashMap. You need to make sure you can always get the value object from the map after you put it with the key object. No matter you change the key object or not. But Immutable object is good enough to achieve that.
Interviewer's intent is to judge your knowledge about Hashing Data Structure. The answer is NO. Making keys in any hashing data structure will cause memory leak.
Map's keys can be of any type, and use Immutable.is to determine key equality. This allows the use of any value (including NaN) as a key. Because Immutable.is returns equality based on value semantics, and Immutable collections are treated as values, any Immutable collection may be used as a key.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With