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.

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.