Updating Java HashMap key

Question

I was just wondering, what would happen if key of a HashMap is mutable, test program below demonstrate that and I am unable to understand when both equals and hashCode methods returns true and same value, why does hashmap.containsKey return false.

public class MutableKeyHashMap {

    public static void main(String []a){

            HashMap<Mutable, String> map = new HashMap<Mutable, String>();
            Mutable m1 = new Mutable(5);
            map.put(m1, "m1");
            Mutable m2 = new Mutable(5);
            System.out.println(map.containsKey(m2));    

            m2.setA(6);
            m1.setA(6);
            Mutable m3 = map.keySet().iterator().next();

            System.out.println(map.containsKey(m2)+"    "+m3.hashCode()+"       "+m2.hashCode()+"       "+m3.equals(m2));   

    }
}
class Mutable {

    int a;

    public Mutable(int a) {

        this.a = a;
    }

    @Override
    public boolean equals(Object obj) {

        Mutable m = (Mutable) obj;
        return m.a == this.a ? true : false; 
    }

    @Override
    public int hashCode(){
        return a;
    }

    public void setA(int a) {

        this.a = a;
    }

    public int getA() {
        return a;
    }
} 

This the output :

true false 6 6 true

Solution 1

The javadoc explains it

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.

Basically, don't use mutable objects as keys in a Map, you're going to get burnt

To extrapolate, because the docs may not appear clear, I believe the pertinent point here is `changed in a manner that affects equals', and you seem to be assuming that equals(Object) is called each time contains is invoked. The docs don't say that, the wording implies they may be allowed to cache computations.

Looking at the source, it seems that because your hashCode returns a different value (was 5, now 6), it's possible that it's being looked up in a different bucket based on implementation details.

Solution 2

You can think of if this way, the Map has 16 buckets. When you give it an object with A == 5, it tosses it into bucket 5. Now you can change A to 6, but it's still in bucket 5. The Map doesn't know you changed A, it doesn't rearrange things internally.

Now you come over with another object with A == 6, and you ask the Map if it has one of those. It goes and looks in bucket 6 and says "Nope, nothing there." It's not going to go and check all the other buckets for you.

Obviously how things get put into buckets is more complicated than that, but that's how it works at the core.

Solution 3

The HashMap puts your object at the location for hash key 5. Then you change the key to 6 and use containsKey to ask the map whether it contains the object. The map looks at position 6 and finds nothing, so it answers false.

So don't do that, then.

Comments

[ptomli]

Commenting on my own answer: it seems to me that the linked implementation doesn't fulfill the obligations of the documentation, because the mutability of type in question affects hashCode and not equals.

[Affe]

Yes but an implementation of hashCode that is legal according to the contract defined by Object will result in functionally equivalent behavior.

[ptomli]

Not quite: "the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified". Since the data used for equals has changed it's permissible too for hashCode to change. The Map documentation implies that equals is the arbiter of equality, while the implementation uses hashCode, erroneously, to find an entry, as far as I can tell. The only savior here is that the Map documentation is not exactly clear about how implementations can use equals during their lifetime. And I don't know the provenance of the linked source.

[Affe]

All the documentation says is if the computation of equals changes, the map might get broken. Since hashCode isn't allowed to change without a change that affects equals, any change that breaks this map implementation is a change that affects equals, thus the documentation covers it.

[ptomli]

@Affe Yes, agreed. (before).equals(X) == (after).equals(X) while (before).hasCode() != (after).hashCode(). The requirements for Map are more stringent than the requirements of Object.equals/Object.hashCode. This doesn't, however, mate well with your earlier comment, re: Object.hashCode, Map requires more of equals/hashCode than Object, the documentation just takes a little digestion.

[Basanth Roy]

unless map resize happened between the time you mutated and the time you tried looking it up again. When resize happens, hashCodes are recalculated.

[smslce]

This makes sense to me . I followed what you said and then added map.put(m1, "m1"); after the line m1.setA(6); . It resulted in "true true 6 6 true".

[starblue]

You should remove it from the hash map before changing the key, otherwise you create a memory leak.