hashmap internal implementation in java with example

HashMap internal implementation 

Hashmap is one of the implementation class of Map interface, it works on the principles of hashing technique.

Hashmap is allowed group of objects as key-value pairs. Each key-value pair is one Entry. In other words, Map is a collection of Entry objects.

Hashmap does not allow duplicate key’s but it allows duplicate values and also allows one null key and any number of null values.

Initial capacity of HashMap is 16.

Each index is called one bucket

Every object has a public final int hashCode() method, that will return integer hash code for every object.

Based on that hash code it will find the bucket and store the key-value pair as an entry in the bucket. The bucket is following the linked list process to store the objects.

Internal code for Entry [key, value, next node, hash value]

static class Entry<K, V> implements Map.Entry<K, V>

{

final K key;

V value;

Entry<K, V> next;

int hash;        

}

        

Let’s we check how HashMap works internally on this below program

package com.collection;

import java.util.HashMap;

import java.util.Map;

public class HashMapTest {

       public static void main(String[] args) {       

              HashMap<Integer,String> map=new HashMap<>();

              map.put(101, "emp1");

              map.put(102, "emp2");

              map.put(103, "emp3");

              map.put(101, "emp4");

              for(Map.Entry<Integer, String> set:map.entrySet()){

                     System.out.println(set.getKey());    //return key

                     System.out.println(set.getValue()); //return value

              }

       }

}

Store objects into HashMap using put()

public V put(K paramK, V paramV)

{     

       //internal implementation

}

If we pass key as null, put() method will check [if (K == null)]. If it is null key, it will store in 0^th bucket position. Because hashcode is zero for the null key so index position also zero.

Whenever we pass the object as a key, first of fall public final int hashCode() method will override and that will return an integer hash code for every object.

Based on that hash code, it will find the corresponding bucket and store the object.

Example :-

              map.put(101, "emp1"); //hashcode : 3117164

              map.put(102, "emp2"); //hashcode : 3117162

              map.put(103, "emp3"); //hashcode : 2163866

              map.put(101, "emp4"); //hashcode : 3117164

find the bucket by dividing hashcode with the maximum capacity of HashMap is 16.

map.put(101, "emp1"); //hashcode : 3117164

by dividing 3117164/16 we will get remainder 12

Now bucket/index position is 12, so that corresponding object map.put(101, "emp1"); will store on that position.

If index is same for two objects

map.put(102, "emp2"); //hashcode : 3117162

map.put(103, "emp3"); //hashcode : 2163866

by calculating hashcode that corresponding index position is 10 for both. In this case, both objects will store in the same index as shown in below diagram.

If hashcode is same for two objects

If hashcode is same for two objects then public final boolean equals() method is overridden and then check for content comparison in two objects.

map.put(101, "emp1"); //hashcode : 3117164            

map.put(101, "emp4"); //hashcode : 3117164

the value will be overridden in the case of keys are same 101, but the key does not override. 

Get the objects from HashMap using get() 

Internall code for get()

public V get(Object paramObject)

  {

    if (paramObject == null) {

      return (V)getForNullKey();

    }

    Entry localEntry = getEntry(paramObject);

    return null == localEntry ? null : localEntry.getValue();

  }

Whenever we call map.get(101), first of fall hashCode() will return hash code for that object. Based on hashcode find the index position.

If both hash code will match [return hashcode and already stored hash code in index] then equals() will check for keys. If key will match then corresponding value emp4 will return.

If two objects are in same index :-

Same as above in this case also first hashCode() and equals() override and check hashcode and key content then return corresponding value

Index position 10 -> entry1[102,emp2, 3117162,103 address] ->  entry2[103,emp3, 2163866,next node]

First check in entry1, if not match go for entry2.

Other important points about HashMap

HashMap is not thread-safe because it is not synchronized. If we want we can make it as synchronized using Collections.synchronizedMap()

             

Map map=Collections.synchronizedMap(hashmap);

       

hashmap is Hashmap object by passing that object into synchronizedMap(hashmap)  method then it will convert into synchronized(thread-safe).

HashMap is a failfast iterator, if we perform any changes on any object while iterating the hashmap objects then we will get ConcurrentModificationException.

So that HashMap is a failfast iterator.

When HashMap reaches the capacity 13^th position, at that time load factor is 0.75. Then only it will increase the capacity of it.

(Initial_capacity_of_hashmap * load factor of hashmap)= 16*0.75=12