Saturday, April 6, 2013

Can the keys in Hashing data structure be made Mutable ?


Interviewer's intent is to know how good you know about Hashing Data Structure

The answer is NO. If we make the keys mutable then the hashcode() of the key will no more be consistent over time which will cause lookup failure for that object from the data structure. Let's analyze this example.
public void testMutableKey(){
        Map testMap = new HashMap<>();
        MutableKey mutableKey = new MutableKey();
        mutableKey.setName("TestName");
        testMap.put(mutableKey, new Object());
        Object o = testMap.get(mutableKey);
        System.out.println("before changing key = " + o);
        mutableKey.setName("abc");    <==== Problematic Instruction
        o = testMap.get(mutableKey);
        System.out.println("after changing key = " + o);
    }

    public static void main(String[] args) {
        MutableHashKey test = new MutableHashKey();
        test.testMutableKey();
    }


Program Output : 
before changing key = java.lang.Object@489bb457
after changing key = null



From the above example we see that as soon as we change the key, we are not able to get the associated object from the Map. 
Let's see what's happening inside
When we put the mutableKey to HashMap then hashcode() is calculated for the key, suppose it comes out to be 11. So the Object123 is successfully inserted into the HashMap at bucket Location 11.
Then we modify the key and try to get the object. HashMap's get() method again calculates the hashcode of the Key, since the Key is changed in between, so suppose hashcode() comes out to be 33 this time. Now the get() method goes to the bucket at address 33 and tries to retrieve the object, but it find nothing over there and returns the null.
Never make changes to the hashmap's key, otherwise the associated object can not be fetched using get() method. Though it will be accessible using other methods which iterate over the entire collection.

No comments:

Post a Comment

Your comment will be published after review from moderator