Working of HashMap internally in Java

HasMap has a static calss named Entry which implements Map.Entry interface. the Entry class looks like:

static class Entry implements Map.Entry{

Final Object Key;

Object value;

Final int hash;

Entry next;

Entrty(int i,Object obj,Object Obj1, Entry entry){

                hash=i;

                Value=Obj1

                next=entry;

                key=obj;

}

Every time we insert a<key, value> into hashmap using .put() method, a new Entry object is created.

Map internally used two data structures to manage/store data:

1.Array

2.Linked List

·         Each index of array is a bucket

·         To identify the bucket for any <key,value>, Hash map use key.hashCode() and perform some operation:

         Bucket (index) =HashMap.indexFor (HashMap.hash(key.hashCode()),  

          entryArray.length)

         It means, two keys with different hashCode can fall under same bucket.

·         If a bucket is empty (table[i] is null) then the Entry object is simply inserted at ith position

          table[i] = new Entry(hash, key, value, null)

·         If a bucket has some values, then the following algo is used:

         Entry  entry = table[i]

        Table[i] = new Entry(hash,key,value,entry)

         It means, the latest entry resides on the top of the bucket.

·         if key already exists in a map, then it just replace the value and return the old value

if (entry.key==key)|| Key.equals(entry.key){

Objectoldvalue=entry.value;

Entry.value=newValue;

Return oldValue;

}

·         Incase of new key, map add the key, value (a bew Entry object with key value) and return null

·         Enty.hash is not the hashcode of key , but HashMap use it own algorithm to create hash based on key.hashcode(). so its like

      entry.hash=HashMap.hash(key.hashCode());

·         HashMap allow single null as key, in that case it creates a dummy Object and use it as key.      

          static final Object NULL_KEY=new Object();

Key Note:

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