How HashMap works internally in Java?

                One of the most important question of the core java interviewers is How hash map works in java or internal.implementation of hashmap. Most of the candidates rejection chances increases if the candidate do not give the satisfactory explanation . This question shows that candidate has good knowledge of Collection . So this question should be in your to do list before appearing for the interview .
                 HashMap works on the principle of Hashing .  To understand Hashing , we should understand the three terms first   i.e  Hash Function , Hash Value and Bucket .

     What is Hash Function , Hash Value  and Bucket ?

         The hashCode() function  which returns an integer value is the Hash function. The important point to note that ,  this method is present in Object class ( Mother of all class ) .
       
        This is the code for the hash function(also known as hashCode method) in Object Class :

    public native int hashCode();

      The most important point to note from the above line :  hashCode method return  int value .
So the Hash value is the int value returned by the hash function .

      What is bucket ?

           
          A bucket is used to store key value pairs . A bucket can have multiple key-value pairs . In hash map, bucket used simple linked list to store objects .
           
          Before start with internal working of HashMap,first you should know this thing,

1. Two unequal object may return same hashcode.
2.  When two objects are equal by equals(), then they must have same hashcode.  

      There are two main  methods used for storing and retrieving values from HashMap.

1) .put() method to put /store values in HashMap
2) .get() method to retrieve data/values from HashMap

1) How put(Key key, Value v) method works internally?

 Lets see implementation of put method:

public V put(K key, V value) {
      if (key == null)
         Nreturn 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;
 }

Let us understand above code step by step,

1) Key object is checked for null. If key is null then it will be stored at table[0] because hashcode for
    null is always 0.
2) Key object’s hashcode() method is called and hash code is calculated. This hashcode is used to find
    index of array for storing Entry object. It may happen sometimes that, this hashcode function is
   poorly written so JDK designer has put another function called hash() which takes above calculated
    hash value as argument.
3) indexFor(hash,table.length)  is used to calculate exact index in table array for storing the Entry
    object.
      The indexFor will return the index of table array, the index calculation is based on hashcode of key and length of table array. This will do the and operation as ,

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

 
4) If two key objects have same hashcode(which is known as collision) then it will be stored in form
    of linkedlist.So here, we will iterate through our linkedlist.

  2) How get(Key key) method works internally?

        
       Here are the steps, which happens, when you call get() method with key object to retrieve corresponding value from hash based collection.
     
    Let's see code,

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;
 }

1) Key object is checked for null. If key is null then value of Object resides at table[0] will be returned.
2) Key object’s hashcode() method is called and hash code is calculated.
3) indexFor(hash,table.length)  is used to calculate exact index in table array using generated hashcode for getting the Entry object.
4) After getting index in table array, it will iterate through linkedlist and check for key equality by calling equals() method and if it returns true then it returns the value of Entry object else returns null.

What happens if two keys has same hashCode?

           If multiple keys has same hashCode, then during put() operation collision had occured, which means multiple Entry object stored in a bucket location. Each Entry keep track of another Entry, forming a linked list data structure. Now , if we need to retrieve value object in this situation, following steps will be followed :

1) Call hashCode() method of key to find bucket location.
2) Traverse  through linked list, comparing keys in each entries using keys.equals() until it return true. So, we use equals() method of key object to find correct entry and then return value from that.

       

Key Notes:--

1) Data structure to store Entry objects is an array named table of type Entry.

2) A particular index location in array is referred as bucket, because it can hold the first element of a LinkedList of Entry objects.

3) Key object’s hashCode() is required to calculate the index location of Entry object.

4) Key object’s equals() method is used to maintain uniqueness of Keys in map.

5) Value object’s hashCode() and equals() method are not used in HashMap’s get() and put() methods.

6) Hash code for null keys is always zero, and such Entry object is always stored in zero index in Entry[].

Related Posts:-- 
1) Internal Implementation of TreeMap in Java  
2) How to iterate the TreeMap in reverse order in Java  
3) Java Program to Count Occurrence of Word in a Sentence  
4) Internal implementation of ArrayList in Java  
5) String Interview Questions and Answers
6) Exception Handling Interview questions and answers