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?

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

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

Solution 3

Hash maps use hash code and equality comparisons to identify a certain key-value pair with a given key. If the has map keeps the key as a reference to the mutable object, it would work in the cases where the same instance is used to retrieve the value. Consider however, the following case:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances and 
// keyOne.equals(keyTwo) is true.

HashMap myMap = new HashMap();

myMap.push(keyOne, "Hello");

String s1 = (String) myMap.get(keyOne); // s1 is "Hello"
String s2 = (String) myMap.get(keyTwo); // s2 is "Hello" 
                                        // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap.get(keyOne); // returns "Hello"
s2 = myMap.get(keyTwo); // not found

The above is true if the key is stored as a reference. In Java usually this is the case. In .NET for instance, if the key is a value type (always passed by value), the result will be different:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances 
// and keyOne.equals(keyTwo) is true.

Dictionary myMap = new Dictionary();

myMap.Add(keyOne, "Hello");

String s1 = (String) myMap[keyOne]; // s1 is "Hello"
String s2 = (String) myMap[keyTwo]; // s2 is "Hello"
                                    // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap[keyOne]; // not found
s2 = myMap[keyTwo]; // returns "Hello"

Other technologies might have other different behaviors. However, almost all of them would come to a situation where the result of using mutable keys is not deterministic, which is very very bad situation in an application - a hard to debug and even harder to understand.

Solution 4

If key’s hash code changes after the key-value pair (Entry) is stored in HashMap, the map will not be able to retrieve the Entry.

Key’s hashcode can change if the key object is mutable. Mutable keys in HahsMap can result in data loss.

Solution 5

This will not work. You are changing the key value, so you are basically throwing it away. Its like creating a real life key and lock, and then changing the key and trying to put it back in the lock.

View more solutions

Comments

[Jared]

I would say, in general, it is inadvisable to use a mutable key. But "safe" is a different question. You can remain "safe" by updating the key-value pair (anytime a key changes). Furthermore, it's absolutely language dependent because behavior is determined by the the contract--it's not inconceivable (though unlikely) that a language would define a key to be a specific object or value, i.e. O1 equals O2, yet O1 points to a different value than O2 in a hash table (again, this behavior wouldn't make much sense).

[Alex Byrth]

Assuming this is Java, by code snippets, programmer can safely rely on native Object.hashcode(). It shall generate a int value based in create order, or other simple, non mutable and unique value.

[toniedzwiedz]

Can you post the source?

[Hulk]

Probable source: From the series "Java theory and practice" - Hashing it out by Brian Goetz, May 27, 2003

[Ruben9922]

I like this answer because of the clear, concrete explanation of what actually happens after the key is mutated. Also for giving another case where it would fail.

[sleske]

This is also in the official Java API docs, e.g. for java.util.Map: "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. ".

[sleske]

While you can technically do this, I don't really see why you would do it. It seems very convoluted (still a good answer though). Just don't use mutable keys, kids :-).

[Clockwork-Muse]

No, the real problem is that mutating a key usually means that it's in the wrong bucket, so things that match the component equality are looking in the wrong spot. Depending on implementation rebucketing the table (by, say, adding more values) will correct this. Note that the usual advice is to avoid Java's clone() method and the Cloneable interface. Not that it would help in all cases, because there are other ways to mutate stored keys (eg, keySet() or entrySet()).

[Jared]

@Clockwork-Muse I think we're talking about two different things. I'm talking about, I have a mutable key object that I use to place into a map; I then expect that if I mutate the key object back to a previous state, it will give back the same entry (value). I think you're talking about a key object that points to a value and then expecting mutating that same key object will still point to the same value; to me this is an unreasonable expectation and not really the problem with mutable keys.

[Clockwork-Muse]

... If you mutate a key back that has been inserted again after mutating and call get(), you're not guaranteed to get either value back. Adding with such a key is just a special case of calling get(), because the map essentially does so under the covers to find out if it needs replacement. From the map's point of view, it doesn't know that you're using the same (mutated) reference as a key in the map, as opposed to a separate key with value equality.

[Jared]

@Clockwork-Muse right...see my answer (where I explain that exact situation).

[aleroot]

@Jared what is not clear in this sentence: "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." ? This is the explanation of why it is bad to use a mutable object as a key in an hash map. They calculate the hash code at insertion...There is no fallacy in here, what is written in that quoted paragraph extracted from the book is simply correct. You are the only one that downvoted the answer, so probably is you that have issues accepting the truth. Probably you just want to create some polemic without any real reason ...

[Jared]

@aleroot Also this isn't a complete explanation. It's not just the hash value that's the problem. That's literally only half of the problem. This doesn't address the fact that a hash table will store the key object for equality checking--perhaps that seems like a trivial problem but I (at least) have found it wasn't. In particular, this can become a problem when trying to optimize Java for memory consumption (when mutable objects are a necessity).

[garg10may]

@aleroot so why can't they simply not allow it, like python which doesn't allow mutable objects as keys

[aleroot]

@garg10may that is a question for Java Design Committee...

[garg10may]

@aleroot yes, but there should be some justification, would you be aware of the same? For me, it looks like a very bad design choice and relies on users to be mature enough to understand that given Java's inherent philosophy is more secure, more explicit, static. If it was another way round, i.e. python allowing it I would have understood.