How does a hash map work internally in Java?

Hash map work internally in Java

Basically, HashMap is an array of Entry class, a static inner class defined in HashMap is as below:

static class Entry implements Map. Entry {

final K key;
V value;
Entry next;
final int hash;

//getters and setters

}

Each element in Hashmap stores in it a key, its value, a reference to next entry in case hash value is the same for two entries, in that case, a linked list will be formed.

Default initial capacity of a HashMap is 16 i.e a HashMap is initialized with a default 16 sized array.

Now, let us see what happens when we put an element into HashMap.
Following is the code for put method in hashmap:

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

private V putForNullKey(V value) {
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

Lets decode the above lines of code;

1)As the HashMap allows values to be stored with null keys in the map, firstly we check if key is null or not.
2)If key is null,putForNullKey method is called and null key value is placed at 0th position of array.
for (Entry e = table[0]; e != null; e = e.next) {//As each element with same hashvalue forms linked list in a hashmap array, we iterate the element using a for loop.If e==null, we add the new element.

3)If key is not null, we need to find the index in the array where we will store our element and this is done using hashing.
int hash = hash(key.hashCode());//We calculate a unique hash corresponding to each element.

int i = indexFor(hash, table.length);//Passing the hash and array length we find the position in array to store the element.

static int indexFor(int h, int length) {
return h & (length-1);
}

As you can see we do & operation between array length and hash value and thus a location is found from 1to16, so suppose hash value is 00000000 00010000 & 00000000 00010000, will give an index of 16.

4)Next we check if an element entry exists at above found index if it doesnt exist we add the new element entry but if an entry element already exists at the index position , here comes the linkedlist into the picture.

5)In the if condition if (e.hash == hash && ((k = e.key) == key || key.equals(k))) , we compare the hash value and a comparison with the equals method written for the object or for the same references.

6)If the above condition is true, the old value is replaced with the new value.
7)If the 5th condition is false, we iterate the linked list until we find the exact key location and put the entry element.