Interior Design of HashMap

HashMap works on principle of hashing.

We have put () and get () method for storing and retrieving data from hashMap.

When we pass an object to put () method to store it on hashMap, hashMap implementation calls hashcode() method hashMap key object and by applying that hashcode on its own hashing funtion it identifies a bucket location for storing value object.

HashMap stores both key+value in bucket.

Map internally used two data structures:

1. Array
2. LinkedList

• Each index of array is a bucket
• To identify the bucket for any <key,value>, Hash map use key.hashCode() and perform some operation:
• It means, two keys with different hashCode can fall under same bucket.
• If a bucket is empty then the Entry object is simply inserted at ith position
• The latest entry resides on the top of the bucket.
• If a key already exists in a map, then it just replace the value and return the old value
• In case of new key,  map add the <key, value> (a new Entry object with key value) and return null
• Entry.hash is not the hashCode of key, but HashMap use its own hash algorithm to create hash based on key.hashCode().

Collision  : If different objects have same hashcode ?

Since hashcode () is same, bucket location would be same and collision occurs in hashMap, 

Since HashMap use a linked list to store in bucket, value object will be stored in next node of linked list.

How to retrieve if two different objects have same hashcode?

We will call get() method and then HashMap uses keys hashcode to find out bucket location.

Since two objects are stored in same bucket, it will traverse through the linked list until find the value object.

After finding bucket location, we will call keys.equals() method to identify correct node in linked list and return associated value object for that key in Java Hash Map