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 ?

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(), they must have same hashcode.

         How does get(Key key) method works internally in HashMap, and Hashtable in Java? 

              Here are steps, which happens, when you call get() method with key object to retrieve corresponding value from hash based collection

a) Key.hashCode() method is used to find the bucket location in backing array. (Remember HashMap is backed by array in Java) Though hashcode() is not used directly, but they are passed to internal hash() function.

b) In backing array or better known as bucket, key and values are stored in form of a nested class called Entry.  If there is only one Entry at bucket location, than value from that entry is returned. 

   
        What happens if two keys has same hashCode?

                           If multiple keys has same hashCode, than during put() operation collision had occurred, which means multiple Entry object stored in a bucket location. Each Entry keep track of another Entry, forming a linked list data structure there.

    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 thought 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 than return value from that. Remember key.equals() method, and this is what Interviewer want to know. I have seen many programmer mentioning value.equals(), which may be due to interview nervousness, but that’s incorrect. Since you don't have value object passed to get() method, there is no question of calling equals and hashCode method on value object.

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[].