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?

回答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.

回答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.

回答3:

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.

回答4:

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.

回答5:

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.

回答6:

As others explained, it is dangerous.

A way to avoid that is to have a const field giving explicitly the hash in your mutable objects (so you would hash on their \"identity\", not their \"state\"). You might even initialize that hash field more or less randomly.

Another trick would be to use the address, e.g. (intptr_t) reinterpret_cast<void*>(this) as a basis for hash.

In all cases, you have to give up hashing the changing state of the object.

回答7:

Behaviour of a Map is not specified if value of an object is changed in a manner that affects equals comparision while object(Mutable) is a key. Even for Set also using mutable object as key is not a good idea.

Lets see a example here :

public class MapKeyShouldntBeMutable {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Employee,Integer> map=new HashMap<Employee,Integer>();

    Employee e=new Employee();
    Employee e1=new Employee();
    Employee e2=new Employee();
    Employee e3=new Employee();
    Employee e4=new Employee();
    e.setName(\"one\");
    e1.setName(\"one\");
    e2.setName(\"three\");
    e3.setName(\"four\");
    e4.setName(\"five\");
    map.put(e, 24);
    map.put(e1, 25);
    map.put(e2, 26);
    map.put(e3, 27);
    map.put(e4, 28);
    e2.setName(\"one\");
    System.out.println(\" is e equals e1 \"+e.equals(e1));
    System.out.println(map);
    for(Employee s:map.keySet())
    {
        System.out.println(\"key : \"+s.getName()+\":value : \"+map.get(s));
    }
}

  }
 class Employee{
String name;

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

@Override
public boolean equals(Object o){
    Employee e=(Employee)o;
    if(this.name.equalsIgnoreCase(e.getName()))
            {
        return true;
            }
    return false;

}

public int hashCode() {
    int sum=0;
    if(this.name!=null)
    {
    for(int i=0;i<this.name.toCharArray().length;i++)
    {
        sum=sum+(int)this.name.toCharArray()[i];
    }
    /*System.out.println(\"name :\"+this.name+\" code : \"+sum);*/
    }
    return sum;

}

}

Here we are trying to add mutable object \"Employee\" to a map. It will work good if all keys added are distinct.Here I have overridden equals and hashcode for employee class.

See first I have added \"e\" and then \"e1\". For both of them equals() will be true and hashcode will be same. So map sees as if the same key is getting added so it should replace the old value with e1\'s value. Then we have added e2,e3,e4 we are fine as of now.

But when we are changing the value of an already added key i.e \"e2\" as one ,it becomes a key similar to one added earlier. Now the map will behave wired. Ideally e2 should replace the existing same key i.e e1.But now map takes this as well. And you will get this in o/p :

 is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@142=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : one:value : 25

See here both keys having one showing same value also. So its unexpected.Now run the same programme again by changing e2.setName(\"diffnt\"); which is e2.setName(\"one\"); here ...Now the o/p will be this :

 is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@27b=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : diffnt:value : null

So by adding changing the mutable key in a map is not encouraged.