CODEWITHSUNDEEP
javahashmap
Basanth Roy
Basanth Roy

Reputation: 6490

How does Java HashMap store entries internally

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.

Upvotes: 9

Views: 11312

Answers (3)

schottsfired
schottsfired

Reputation: 131

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.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533530

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, both final and immutable.

Upvotes: 1

Louis Wasserman
Louis Wasserman

Reputation: 198103

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.

Upvotes: 9

Related Questions