Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Are mutable hashmap keys a dangerous practice?

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?

like image 420
donnyton Avatar asked Oct 20 '11 20:10

donnyton


People also ask

Can we use mutable objects as keys in HashMap?

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.

Can we create HashMap key immutable or mutable will be better?

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.

Are hash maps mutable?

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.

Are map keys immutable?

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.


2 Answers

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.

like image 199
aleroot Avatar answered Nov 21 '22 09:11

aleroot


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.

like image 35
sbridges Avatar answered Nov 21 '22 08:11

sbridges