Do HashMap values need to be immutable?

Question

I understand that keys in a HashMap need to be immutable, or at least ensure that their hash code (hashCode()) will not change or conflict with another object with different state.

However, do the values stored in HashMap need to be the same as above*? Why or why not?

* The idea is to be able to mutate the values (such as calling setters on it) without affecting the ability to retrieve them later from the HashMap using immutable keys. If values are mutated, can that break their association to the keys?

My question is mainly concerning Java, however, answers for other languages are welcome.

Answer 1

No. In general the characteristics of a hash map data structure do not depend upon the value. Having keys be immutable is important because the underlying data structures are built using the hash of the key at the time of insertion. The underlying data structures are designed to provide certain properties (relatively fast look up, fast removal, fast removal, etc...) all based upon this hash. If this hash were to change then the data structure with these nice properties based upon a hash which has changed will be invalidated. If you need to "modify" a key one general approach is to remove the old key and re-insert the new key.