How HashMap works in Java

First of all, lets keep one thing in your mind that, every collection API internally implements either Array or LinkedList to store objects. Primary Hashmap works in Hashing principle and calculating Hashcode is a key. unique hashcode for each object will ensure fast processing. So before implementing any collection API, strong knowledge of Hashcode and equals method is must.

Now, I will try to explain step by step, how Hashmap works.

1) Let's Create an Instance of Hashmap 

Map

Here, as soon as you write new HashMap JVM call default Constructor of HashMap which internally calls Parameterized constructure of HashMap with default size of 16. This constructor Initalize the ElementArray with Default Size and set basic parameters like elementCount, loadfactor (0.75f).

ElementArray is nothing but an Array of Entry Type. 

Now what is an Entry ? 

Entry is an static inner class of HashMap which is being used to hold the Key and Value with equals and Hashcode implemented, 

So when you put something in to Map, it is an Entry object which is being stored in ElementArray.

Syntax - 

static class Entry extends MapEntry 

Creating Entry object and putting it into Array.

Entry createHashedEntry(K key, int index, int hash) {
        Entry entry = new Entry(key, hash);
        entry.next = elementData[index];
        elementData[index] = entry;
        return entry;

    }

So, now HashMap object created and memory allocated to store objects in terms of key and value.

2) Put object into HashMap - 

map.put(object, object);

Above statement calls put method of HashMap. 

public V put(K key, V value) which internally calls putImpl(K key, V value) and return type is Value.However, there is no use of returned value but still if you call it put and wanted to assign reference to it you can do that.

put method, first checks if provided key is null, as HashMap supports one Null key, you can very well use Null as key. If key is Null then it first checks if Entry object having Null as key is already available in elementArray.  Null as key get stored in index 0 all the time. So it directly fetches from elementArray[0] whenever requested.

If no Entry object found then it creates new Entry object having Null as key and value ( Whatever we have passed) and store it into index 0 of elementarray.

If Key is not null then it first calculate the Hashcode of key and then the index. Once location in Array identified, Entry objects,get created and inserted in the same location.

As Hashcode can be same for two objects, depends on hashing algorithm applied, you can land up in a situation where two keys having same Index in array. This is called collision and to handle this Java has implemented LinkedList concept for storing entry objects.

Each entry object having a next field which holds the reference of another key having same hashcode.

As soon as array 75% filled ( load factor 0.75), array size gets doubled.

To avoid this programmer should write strong hashing algorithm while overriding hashcode. Making immutable object as key can solve the problem and improve the performance.

3) Get Object from HashMap

map.get (key)

If provided key is null then directly entry object will be retrieved from elementArray[0] and will check if key is null, once get value of entry will be returned.

If provided key is not null then first it will calculate hashcode of key and identifies the location (Index) . Will extract the Entry Object from elementArray[index]. It will iterate whole entry object as it maintain LinkedList and compare hashcode of stored key and provided key, if it is same then will apply equal method to compare the content of key. If both are same it will return the value of given key.

Sample code of getting object- 

int hash = key.hashCode();

        int index = hash & (elementData.length - 1);

int storedKeyHash = keyHash & 0xFFFFFFFE;

Entry m = elementData[index];

while (m != null && (m.storedKeyHash != storedKeyHash || !key.equals(m.key))) {

m = m.next;

}

Note - String, Integer and other wrapper classes are considered as good key

String, Integer and other wrapper classes are natural candidates of HashMap key, and String is most frequently used key as well because String is immutable and final,and overrides equals and hashcode() method. Other wrapper class also shares similar property. Immutability is required, in order to prevent changes on fields used to calculate hashCode() because if key object return different hashCode during insertion and retrieval than it won't be possible to get object from HashMap. Immutability is best as it offers other advantages as well like thread-safety, If you can  keep your hashCode same by only making certain fields final, then you go for that as well. Since equals() and hashCode() method is used during retrieval of value object from HashMap, its important that key object correctly override these methods and follow contact. If unequal object return different hashcode than chances of collision will be less which subsequently improve performance of HashMap.