sagar sagar - 2 months ago 13
Java Question

can we have a nested map as key within other map?

I have just started implementing data structures in Java and was wondering can we have a situation like this.

Map<HashMap<String,String>,String> map = new HashMap<HashMap<String,String>,String>();


And if yes ,, please give a small example.

If you don't found question relevant ,, please mention in comments,

Answer

You can do this, but you should not do so in most cases.

The key to a map needs to be constant and its equals and hashcode need to be set up to give the correct behavior. If you modify a key after adding it into the map then you invalidate the map.

A HashMap can be modified so should not be used as a key.

To explain why changing it is a problem you need to know how hashmaps work. This is very simplified but lets say you have a HashMap H containing two buckets. Lets call them B0 and B1.

Whenever you add an Object to the HashMap it looks at that objects hashCode. If the final bit is 0 then it goes in B0, if it is 1 then it goes in B1.

Now when looking up an object it looks at the hashCode and immediately goes to the right bucket, it then only needs to search the objects in that bucket to find the object it needs.

By using more buckets than just 2 you can reduce the number of items in each bucket by 2, 4, 8 or more times and hence reduce the number of objects you need to check.

However lets say you put an object in the map and it gets added to B0. You then change the object and the hashCode changes so the last bit is now 1.

if you do map.contains(obj) you will get the result false because it will look at the hashCode, jump straight to B1 and only scan that for the object. But the object was placed in B0 because that is what the hashCode had at the time it was inserted.

This is why the hashCode must be constant for any object being used as a key in a HashMap, as otherwise you can "lose" these keys.

Comments