Internal Working Of HashMap

This is the most asked question in Java interviews!!!!

Lets understand basics of HashMap which will make it easier to understand how HashMap works internally.

HASHMAP —

1. The class which implements the map interface of the Java collection
2. Allows us to create key-value pairs, HashMap keys are unique identifiers
3. Values can be retrieved using the keys under which it is stored.
4. HashMap is not a thread-safe implementation
5. put() method is used to insert mapping into the hashmap and using the get() method we can pass the key and get the corresponding value for that key from the hashmap
6. Hashmap doesn’t maintain the insertion order of the elements
7. We can have 1 null key and as many as we want null values in HashMap

Now let’s see one simple example of creating and iterating HashMap :

import java.util.HashMap;
import java.util.Map;

public class Test {
  public static void main(String args[]) {
    Map<String, String> map = new HashMap<>();
    //Inserting key Value Mapping into hashmap

    map.put("Name", "John");
    map.put("Age", "25");

    //Iterating Hashmap using for loop
    for (Map.Entry<String, String> m : map.entrySet()) {
      System.out.println("KEY : " + m.getKey() + " Value : " + m.getValue());
    }
    //Getting value by passing key to get method
    String name = map.get("Name");
    System.out.println("Getting value by key: " + name);
  }
}

Output —

KEY : Age Value : 25
KEY : Name Value : John
Getting value by key: John

Note: If we try to put the same key again it will be overridden with the earlier key, value pair, for eq in the above example if we put the same key as below

    Map<String, String> map = new HashMap<>();
    map.put("Name", "John");
    map.put("Age", "25");
    map.put("Name","Bob");
    //Iterating Hashmap using for loop
    for (Map.Entry<String, String> m : map.entrySet()) {
      System.out.println("KEY : " + m.getKey() + " Value : " + m.getValue());
    }

Output will be like this —

KEY : Age Value : 25
KEY : Name Value : Bob
Getting value by key: Bob

Now that we know how hashmap works with get and put methods let's understand how it works internally, what is the logic behind it

Nodes: Hashmap contains an array of nodes internally, each node contains the following elements:

1. int hash
2. K key
3. V value
4. Node next

Hashing — Hashing is the process of converting an object into an integer form

Hashcode method — Use to get the hashcode of the object

Equals Method — Use to compare if objects are equal

Buckets: This is an element of an array used to store nodes, two or more nodes can have the same bucket, in that case, a linked list-like structure gets created and used to connect the nodes. Buckets are different in capacity, the default size of the bucket is 16.

Index Calculation : Index is used to minimize the size of the array, as key may be large enough to generate an array , hashcode generated by this key can be large enough to utilize more space and can easily through ArrayIndexOutOfBound Exception.

Lets take an empty HashMap

HashMap map = new HashMap();

Here the size of HashMap will be taken as 16 — default

HashMap

Inserting key-value pair

map.put("Name", "John");

1. Calculate hashcode of key Name — hashcode of the key here will be 66965 (as hashcode method will be used to calculate hashcode, hashcode is integer form of the object, and to create that hashing mechanism will be used)

NOTE: You can try or check the hashcode of your key using the hashcode method in this example it will be :

System.out.println(map.get(“Name”).hashCode()); // 66965

2. Calculate the index by using the index method, to calculate the index below formula is used index = hashCode(key) & (n-1).

so, for this node index will be index — 5 , this means that this node will be stored at index 5

3. Create Node Object -

int hash = 66965
String key = "Name"
String value = "John"
Node next = null

4. Place this object at index 5 if no other object is present there.

Created node in hashmap

In case any other object was already present at index 6, a linkedList like structure would have been created and the node will be added to the next node in the same index.

This is how data gets inserted in the hashmap.

Now let’s get some data from the hashmap using the get method.

 String name = map.get("Name");
 System.out.println("Getting value by key: " + name);

1. Calculate the hash code of Key {“Name”}. It will be generated as 66965.
2. Calculate the index by using the index method it will be 5.
3. Go to index 5 of the array and compare the element’s key with the given key. If both equal then return the value, otherwise, check for the next element if it exists.

And this is how we put and get data from hashmap internally.

Lets answer few questions that are also asked in most of the java interviews about hashmap.

What is the collision in HashMap and how it is handled?

Collision happens when 2 keys returns the same hashcode value which results in generating the same index, in this case, HashMap use chaining or LinkedList like structure in bucked to store multiple elements with same hashcode value.

2. Can you store null key in java hashmap ?

Yes. HashMap does allow to store 1 null key.

3. Difference between HashMap and HashTable?

HashMap and HashTable are very similar except that HashTable allows Synchronization, HashMap doesn’t, and HashTable doesn't allow any null keys or null values.