Why do we need an Immutable key in an HashMap

In my previous posts, I explained the contract of equals and hashCode methods and also explained how the HashMap works in Java. If you have not read it I would suggest you to strongly read it before you read this topic.

To understand this topic we should first know what happens if the key is mutable.

Let's take the put operation for example
Whenever we implement hashCode method, we need to keep in mind that it should not include fields which are mutable.

If it does, then clearly the hashCode implementation will return different value then the previous time it was invoked.  i.e. when the state of the object is modified, then the hashCode will differ.

What happens then, is that during the process of insertion of the key, value pair, the hash value calculated for the key, in order to find the index of the bucket differs from the earlier one (Note: The post on how HashMap works will come in handy here for clear understanding) and the key, value would be place in a different bucket. As a result, the earlier node in the bucket list will be never reached and hence would be dangling forever.

So what happens if the key is modified and we try to retrieve?
Imagine, the key, value pair is already placed in a specific location in the bucket based on the key. Now if the Key is mutated, a new hashCode is formed, it causes indexFor method to return a different index to look for the key and hence won't be found, resulting in null value to be returned.

Hence, it is strongly advised to have they key as immutable so that the HashMap does not loose track of the bucket where they key was placed. This is the case for all Hash based collections.