How HashMap Works Internally in Java? Internal implementation of HashMap

Java Hashmap uses key/value concepts to store the item. Some basics like -

                       HashMap map = new HashMap();

                       map.put(key, value); /// add the item to map

                       map.get(key);// get the item from map.

In this blog I will tell you how it works internally. So to know internally let see below HashMap API main code (code is not full only required part I am showing here)-

public class HashMap<K,V>    extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, serializable

{

     transient Entry[] table;

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

        final K key;

        V value;

        Entry<K,V> next;

        final int hash;

…………………

………………….

}

     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<K,V> 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;

    }

    public V get(Object key) {

        if (key == null)

            return getForNullKey();

        int hash = hash(key.hashCode());

        for (Entry<K,V> e = table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

        if (e.hash == hash && ((k = e.key)==key||key.equals(k)))

                return e.value;

        }

        return null;

    }

}

 

As you can see in above code main is Entry[], get() ,put() And Entry inner class.

Let see one by one how put() method is working here- 

First line of put method() - key object is checked for null. If key is null, value is stored in table[0] position. Because hash code for null is always 0. Then on next step, a hash value is calculated using key’s hash code by calling its hashCode() method. This hashcode value is used to calculate index in array for storing Entry object. This index is nothing but bucket index. That means all the item in HashMap is stored in Bucket. you can see from below diagram, HashMap has Entry[] array i.e array of bucket.

As you have seen hashcode() is required to get the index value of bucket that means if we want to store key as a object in HashMap then key object should always override the hashCode() method.Now

assume we are storing below class as a key in HashMap-

            class Key{

                  int key;

                  Key(int key){

                     this.key = key;

                  }

                  public int hashCode(){

                      return 10;

                  }

            }

 

 So to add as a key in HashMap I will use below code -

                      HashMap map = new HashMap();

                      map.put(new Key(5), “123”); // key object has hascode value 10

                      map.put(new Key(6),”234”); // key object has hashcode value 10

 So, in this case key hashCode() is always returning 10. So now see in put method of HashMap always will return same bucket number. That means all the key will store in same bucket because hashcode is same for all the key. So this type of condition is called HashMap collision.

See below diagram this diagram shows that 3 entry object in bucket number to 0 and 2 entry object in nth bucket.

Now if bucket is same then how item will store in hashMap or how two different objects will be stored in same array location. Here is the trick all the item which has same bucket number will be stored in linked list. See the Entry inner class of HashMaps has an attribute “next”. This attribute always points to next object in chain. So, in case of collision, Entry objects are stored in LinkedList form. When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry?? If there is no entry already present, Entry object is stored in this location. If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current Entry object becomes next node in LinkedList. If next variable is not null, procedure is followed until next is evaluated as null. But what happen if we try to add another value with same key entered before. Logically, it should replace the old value ,but not.

after determining the index position of Entry object, while iterating over LinkedList on calculated index, HashMap calls equals method on key object for each Entry object. All these Entry objects in LinkedList will have similar hash code but equals() method will test for true equality. If key.equals(k) will be true then both keys are treated as same key object. This will cause the replacing of value object inside Entry object only.

Now let see how get method works-

You can see in get method of HashMap also we need hashCode() of key and then hash function which will calculate the bucket number once bucket number is returned HashMap apply same logic which was applicable to put method. i.e hashcode() method + equals() check for same key if key not found then return null.

  
And make a note that if hashCode is same for key Object then performance will be slow because internally it check everytime hashCode() and equals() and maintain LinkedList and to find the item it has to traverse the linkedlist sequentially,  which will downgrade the performance. so, during the code always avoid the HashMap collision case.