String as key in hashmap [duplicate]

Question

I have read a lot of posts in the past one hour, but I am still not very clear with the concept of using immutable objects as keys in a Hashmap. I have a hashmap that has its key as a String. The value in the hashmap is MyStore, where MyStore represents information regarding stores I own. The String represents address. In my code, the logic I have is, I first look in the map for that key, if present --> get its value, if its not present put it in hashmap. My manager just told me the key will change in the future, that is address of my stores will change in the future. He said in that case, my logic of first checking if the key exists won't work. I don't understand what he means here. I want to understand the below points very clearly -

1. Difference between mutable and immutable keys for a hashmap.
2. What happens if you use a immutable key that can change? - I know this doesn't make sense, but I want to clearly understand what my manager is talking about here.
3. Some posts talk about Strings if used as keys in a hashmap cache their hashcode -What does this mean?
4. If lets say I used mutable objects as keys in my hashmap that implemented hashcode and equals, then will it work? I am assuming it will because if the key changes, the contains method will look if the key is present. If it is not present, it will put the entry so you can get it in the future.

I don't mean to create a duplicate post if this has been discussed before. If I missed reading the post that has answers to all my questions, please point me to it. If not, please explain in layman terms the above questions I have so it is useful in the future for other readers :). Feel free to edit my post's subject so in future if anyone has a similar question, they land here directly :)

Answer 1

First : how does a HashMap work?

Basically it has an array and when you put a key-value pair in the map, it is stored in one of the positions in the array. The position in the array is chosen based on the result of the key's hashCode() passed to a hashing method. Why is that? Well, if you request the value for a certain key, the index in the array to find the key and its associated value can simply be recalculated to find the index in the array again. (Some more logic is needed to deal with keys that map to the same index, but I'm just trying to get you to understand the basic mechanism) Then equals() is used to verify if the key at the calculated index is indeed the requested key.

1. From this it should be a bit more clear why immutable keys are better than mutable keys. An immutable key will always keep the same hashCode() value, and the hashing function will find the correct bucket ( = index in the hashMap's array) again.

   That doesn't mean mutable keys cannot work. A mutable key will work if mutations on the key do not affect the hash code or if the keys are simply not mutated as long as the hashMap is used.

2. How can an immutable key change? Well, the key itself may not be able to change, but the key-value mapping can change in business logic. If you create a map, using the address as a key, you rely on the fact that a store's address will not change. If a store's address changes, you'll not find it in the Map using its new address as a key. Your manager has a valid point.

3. the speed of finding a key in a Map highly depends on the speed of calculating the hashCode. For a String this calculation loops over all the characters in the String. If you use long Strings as keys and have a lot of Map access this may lead to a performance bottle neck. Java's String implementation therefore caches the hash value, so it will be calculated only once. However you'll only avoid calculating the hash code if you use the same String instance again (new instances will not have the cached value). You may intern() the keys you use, but consider this only if it can be shown that there really is a performance bottle neck, as String interning does come with its own overhead.

4. as explained in 1 : mutable keys can work if their hash code is not affected by mutations. e.g. using a Customer as key, where the hashCode() is based only on the customer's name, then a Customer implementation that only does not allow the name to change, yet allows other values to change, is a reliable key.