Internal working of HashMap 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 a Hashmap stores in it a key, its value, reference to next entry in case hashvalue is 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, lets 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 above condition is true, old value is replaced with new value.
7)If 5th condition is false, we iterate the linked list till we find the exact key location and put the entry element.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s