How does Java HashMap store entries internally

Question

Say you have a key class (KeyClass) with overridden equals, hashCode and clone methods. Assume that it has 2 primitive fields, a String (name) and an int (id).

Now you define

KeyClass keyOriginal, keyCopy, keyClone;
keyOriginal = new KeyClass("original", 1);
keyCopy = new KeyClass("original", 1);
keyClone = KeyClass.clone();

Now

keyOriginal.hashCode() == keyCopy.hashCode() == keyClone.hashCode()
keyOriginal.equals(keyCopy) == true
keyCopy.equals(keyClone) == true

So as far as a HashMap is concerned, keyOriginal, keyCopy and keyClone are indistinguishable.

Now if you put an entry into the HashMap using keyOriginal, you can retrieve it back using keyCopy or keyClone, ie

map.put(keyOriginal, valueOriginal);
map.get(keyCopy) will return valueOriginal
map.get(keyClone) will return valueOriginal

Additionally, if you mutate the key after you have put it into the map, you cannot retrieve the original value. So for eg

keyOriginal.name = "mutated";
keyOriginal.id = 1000;
Now map.get(keyOriginal) will return null

So my question is

when you say map.keySet(), it will return back all the keys in the map. How does the HashMap class know what are the complete list of keys, values and entries stored in the map?

EDIT So as I understand it, I think it works by making the Entry key as a final variable.

static class Entry<K,V> implements Map.Entry<K,V> { 
 final K key; 

(docjar.com/html/api/java/util/HashMap.java.html). So even if I mutate the key after putting it into the map, the original key is retained. Is my understanding correct? But even if the original key reference is retained, one can still mutate its contents. So if the contents are mutated, and the K,V is still stored in the original location, how does retrieval work?

EDIT retrieval will fail if you mutate the key after putting into the hashmap. Hence it is not recommended that you have mutable hashmap keys.

• user177800: why not just look at the source yourself, it is public and easily accessible
• Nim: if it didn't it wouldn't be much of a data structure now would it? How do you think it's able to lookup the particular key you want?
• Alexander Pavlov: The source for the curious.
• Basanth Roy: Looking up a single key is just a question of calculating hashCode and then comparing each collided key using equals. But the HashMap needs to be aware of what are all the keys stored in it; without the client passing in a key. So The answer by Louis below looks like how that is happening.

Answer 1

HashMap maintains a table of entries, with references to the associated keys and values, organized according to their hash code. If you mutate a key, then the hash code will change, but the entry in HashMap is still placed in the hash table according to the original hash code. That's why map.get(keyOriginal) will return null.

map.keySet() just iterates over the hash table, returning the key of each entry it has.

• Basanth Roy: Thanks. "If you mutate a key, then the hash code will change, but the entry in HashMap is still placed in the hash table according to the original hash code." I read the source code. So as I understand it, I think it works by making the Entry key as a final variable. static class Entry<K,V> implements Map.Entry<K,V> { final K key; (docjar.com/html/api/java/util/HashMap.java.html). So even if I mutate the key after putting it into the map, the original key is retained. Is my understanding correct?
• Louis Wasserman: It holds a reference to the key. If you mutate the key, then basically, the entrySet() of the HashMap will see the modified key, but get(key) will be looking in the wrong place, so it'll return null when you try map.get(key). Basically, having mutable keys in a Map is just asking for trouble, and actually going ahead and mutating keys in a Map is like shooting yourself in the kneecaps.
• Basanth Roy: Thanks again. But what I still haven't understood is this. You have keyOriginal and keyCopy with the same field values within them. Now you put keyOriginal in the map. Say it goes into position 100 in the internal hashmap entry table. Now you mutate keyOriginal. It is still stored in position 100. Now if you say map.get(keyCopy), it does return the original associated value. How is it able to do that if keyOriginal.equals(keyCopy) is false ?
• Louis Wasserman: Have you tested that? I would be very surprised if that's true. I would strongly expect map.get(keyCopy) to return null.
• Basanth Roy: Yes, I have tested that. I will add the test code in a new question. I can't add it here since it would be too long.

Answer 2

If you change the entry but not the hashCode, you are safe. For this reason it is considered best practice to make all fields in the hashCode, equals and compareTo methods, both final and immutable.

• Basanth Roy: Thanks. Good info. -- "If you change the entry but not the hashCode, you are safe." -- I would add that you are still not safe since equals will fail.
• Basanth Roy: So I guess it is safe to say that if you mutate the key (hashCode is different and equals is false) after adding to map, then your retrieval will fail.
• Peter Lawrey: Unless that is what you intended. ;) If it has to be mutable, you can remove the key, update it and add it back. Its only a problem if you change the key while its a key to a map (or an element of a Set for the same reason)
• Basanth Roy: Yes true, that was not my intention in this case.

Answer 3

Simply put, the HashMap is an object in your computer's memory that contains keys and values. Each key is unique (read about hashcode), and each key points to a single value.

In your code example, the value coming out of your map in each case is the same because the key is the same. When you changed your key, there is no way to get a value for it because you never added an item to your HashMap with the mutated key.

If you added the line:

map.put("mutated", 2);

Before mutating the key, then you will no longer get a null value.