Internal Working of HashMap in Java

Introduction

Is there any data structure that can perform insertion, deletion, and searching in less time than arrays and other data structures?

The answer is, Yes!

HashMap is a Data Structure that uses "key-value" pairs to store items. As the name suggests, they are good at mapping. HashMap enables us to map one object to another. It could be a String, an Integer, or a multi-fielded object.
It is an important data structure and its implementation is provided in Java. But, in this article, we will see how to create our own hashmap using arrays. 

Before that, let’s understand the HashMap class provided by Java.

Must Recommended Topic, Hash Function in Data Structure.

What is Hashmap In Java

A map contains key and value pairs. Java has the Map interface and HashMap is a hashtable-based implementation of this interface. The HashMap class of Java is almost the same as Hashtable, except that it is unsynchronized and permits nulls. 

HashMap provides constant-time performance for the basic operations such as insertion and deletion. 

In this article, we’ll see the basic implementation of HashMaps in Java using an array of linked lists. Let’s start by seeing an example.

Examples of a HashMap

Let’s say we’re given some key-value pairs, we’ve to find its appropriate index by performing hashing. If the index of each key-value pair is different(as given below), there are no collisions.

Wondering what are collisions?

“A collision in a HashMap is a state in which two or more keys produce the same hash value and point to the same bucket or index.”

Let’s see another example. In the example below, keys k2 and k3 are pointing to the same index and are in the same bucket. This is the case of collision.

Now, let’s move on to the solution of this problem.

How to avoid Collisions?

In order to avoid collisions, we’re implementing HashMap using linked lists. 

Why exactly are linked lists? 

If we wanted to resolve the problem of collisions, there was a choice to use just arrays only. We could move to the next index once there is a collision on some. 

But the problem with arrays is that their size needs to be defined. And since in the worst case there can be many collisions, using an array is not so efficient. 

So we basically need a data structure whose size doesn’t need to be defined. Thus, an array of linked lists is the most appropriate. And the linked lists are referred to as buckets here, which means we have an array of buckets.

How are elements stored in this array of linked lists?                       

Source: Deepak Vadgama 

Here, the key-value pairs pointing to the same index in the array are stored in the linked list at that index. Like at the first index, 3 key-value pairs are stored in the linked list. 

Recommended: Try to implement this Problem yourself before moving on to the solution

Implementation

Defining class

First, we’ll define and initiate a class representing a node of a linked list which will have two attributes, namely, key and value.

First, we’ll define and initiate a class representing a node of a linked list which will have two attributes, namely, key and value.
private class Node{  // contains two parameters - key and value
	K key;   
	V value;

	Node(K key, V value) {
		this.key = key;  // initialising the key  
        this.value = value;   // initialising the value
	}
}

Initializing the buckets

The steps are as follows:

• Declare and initialize a size variable to 0.
• Declare an array of linked lists 
• Call an initbuckets() function which initializes each bucket with an empty linked list

Implementation of initialization

private int size; // n
private LinkedList<Node>[] buckets; // N = buckets.length

public HashMap() {
	initializebuckets(4);
	size = 0;
}

private void initializebuckets(int N) {
	buckets = new LinkedList[N];
	for (int i = 0; i < buckets.length; i++) {
		buckets[i] = new LinkedList<>();
	}
}

Let us now discuss about hashCode() and equals() methods:

Insertion

Before we proceed, let’s have a recap of what’s hash code is.

Hash code in java is an integer associated with each object which helps in the hashing method by finding the index of the array where the object should be placed. This integer is calculated by calling a hashCode() function which is inbuilt in the object class. 

The steps are as follows : 

• First, we create a bucket to store all the key values with the initial capacity set to 6.
• Then in the insert function, we get the hash code of the key we want to insert. hashCode() function is used for that. The hash code is usually an integer. As you would already know, two different objects can have the same hash code, as there might be an infinite number of keys but a finite number of integers. 
• Using hash code, we find the module of (hash Code % array_length), in the hashfn() function, and that would give the index of the array in which this key will be placed. Again, two different hash codes can map to the same index. 
• Then, we got to the linked list present at this index. 
• If in that linked list there is no such key present (which is basically being checked by the getIndexWithinBucket() function), we make a new node with the key-value pair, place it at the index and increase the size by 1.
• Otherwise, if there is any such key present, we update the value of “value” for that key. 

Implementation of Insertion

The function put() is used for inserting. Now, let’s see the implementation of the above approach.

// function for inserting a key-value pair
public void put(K key, V value) throws Exception 
{ 
	int bi = hashfn(key);   // getting the value of index of bucket
	int di = getIndexWithinBucket(key,bi);   // getting the value of index
	// inside the bucket
	if(di!=-1)
	{ 
		// if the key is already present
		Node node = buckets[bi].get(di);  // node at index di in the bucket bi
		node.value = value; // updating the value
	}
	else
	{  
		// if the key is not already present 
		Node node = new Node(key,value);  // make a new node with that key-value
		buckets[bi].add(node);  // add it on index bi
		Size++;  // increase the size
	}
}
    
// function that calculates the index of the bucket in which key lies
private int hashfn(K key)
{ 
	int hc = key.hashCode();  // inbuilt function for calculating hashCode
	return Math.abs(hc)%buckets.length; // returning the absolute value of the
	// hashCode with bucket length so that we get an index which is in the
	// range of the array
}
    
// Function that returns the index in the linked list at position bi where
// key==key
private int getIndexWithinBucket(K key, int bi)
{
	int di = 0;
	for(Node node : buckets[bi])
	{
		if(node.key.equals(key))
		{ 
			// if key==key, return the index
			return di;
		}
		di++; // otherwise, keep moving to the next index 
	}
	
	return -1;  // if we've searched the whole linked list and the key is not
	// present, return -1.
}

Retrieval

To retrieve a value with the help of key, get() function is used.

The steps are as follows : 

• First, compute the hash code of the key-value you want to retrieve.
• Find the index by taking the modulo (hash code% array_size). hashfn() does this.
• Call the getIndexWithinBucket() function for that index. What it does is, checks if there is any such already present. If there is, it returns the index of the linked list at which it is present. Otherwise, it just returns -1.
• When we have got the bucket index (bi) and the linked list (di), we just return the value of the node at that index. 
• And if we’ve received -1 from the getIndexWithinBucket() function, we just return null because the key isn’t there in the hashmap.

Implementation of Retrieval

private int hashfn(K key){
	int hc = key.hashCode();
	return Math.abs(hc)%buckets.length;
}
    
private int getIndexWithinBucket(K key, int bi){
	int di = 0;
	for(Node node : buckets[bi]){
		if(node.key.equals(key)){
			return di;
		}
		di++;
	}
	return -1;
}

public V get(K key) throws Exception {
	int bi = hashfn(key);    // index of the bucket
	int di = getIndexWithinBucket(key,bi); //index of the position in that 
	//bucket
	if(di!=-1){ // if the key is present at di, return its value. Otherwise, 
		// Return null
		Node node = buckets[bi].get(di);            
		return node.value;
	}
	else{ 
		return null;
	}
}

Check if the HashMap contains a given key

To check if a key is present in the hashMap or not, we use the containsKey() function which returns a boolean value (true if the key is present, otherwise false). 

The steps are as follows:

• First, compute the hash code of the key-value you want to retrieve.
• Find the index by taking the modulo (hash code% array_size). hashfn() does this.
• Call the getIndexWithinBucket() function for that index. What it does is, checks if there is any such already present. If there is, it returns the index of the linked list at which it is present. Otherwise, it just returns -1.
• If the value returned by the getIndexWithinBucket() function is -1, it means that the key is not in the HashMap, so just return false. Otherwise, return true.

Implementation

public boolean containsKey(K key) {
	int bi = hashfn(key);  // index of the bucket
	int di = getIndexWithinBucket(key,bi);  //index of the position in that 
	//bucket
	if(di!=-1){  //if the di value is not equal to -1 return true, otherwise  //false
		return true;
	}
	else{
		return false;
	}
}

private int hashfn(K key){
	int hc = key.hashCode();
	return Math.abs(hc)%buckets.length;
}
    
private int getIndexWithinBucket(K key, int bi){
	int d1 = 0;
	for(Node node : buckets[bi]){
		if(node.key.equals(key)){
			return d1;
		}
		d1++;
	}
	return -1;
}

Deletion

To delete a key-value pair, the remove() function is used.

The steps are as follows : 

• First, compute the hash code of the key-value you want to retrieve.
• Find the index by taking the modulo (hash code% array_size).hashfn() function. 
• Call the getIndexWithinBucket() function for that index. What it does is, checks if there is any such already present. If there is, it returns the index of the linked list at which it is present. Otherwise, it just returns -1.
• When we have got the bucket index (bi) and the linked list (di), just call the .remove() function and reduce the size by 1.
• And if we’ve received -1 from the getIndexWithinBucket() function, we just return null because the key isn’t there in the hashmap.

Implementation of Deletion

private int hashfn(K key){
	int hc = key.hashCode();
	return Math.abs(hc)%buckets.length;
}
    
private int getIndexWithinBucket(K key, int bi){
	int di = 0;
	for(Node node : buckets[bi]){
		if(node.key.equals(key)){
			return di;
		}
		di++;
	}
	return -1;
}

public V remove(K key) throws Exception {
	int bi = hashfn(key); // index of the bucket
	int di = getIndexWithinBucket(key,bi); //index of the position in that 
	//bucket
	if(di!=-1){  // if the key is present at di, remove it and decrease the size
	// by 1. Otherwise, return null
		Node node = buckets[bi].remove(di);
		size--;
		return node.value;
	}
	else{
		return null;
	}
}

Displaying the whole keyset 

To display the whole keyset present in the HashMap, we use the keyset() function. 

The steps are as follows: 

• Declare an array of keys (named keys), which will basically store all the keys and we’ll return it.
• Just traverse through each bucket, bucket[bi], and for each node in bucket[bi], add the key of the node in the keys array.
• Return the keys array.

Implementation of displaying the whole keyset

public ArrayList<K> keyset() throws Exception {
      ArrayList<K> keys = new ArrayList<>();  //Declare the array of keys, which //will contain all the keys
      for(int bi =0;bi<buckets.length;bi++){
          for(Node  node:buckets[bi]){  //For each node in the bucket[bi]
              keys.add(node.key);  //add the key in the keys array
          }
      }
      return keys;  // return the keys array
}

Size of HashMap 

To find the size of HashMap, the size() function is used.

The steps are as follows: 

• We’ve already declared and initialized the size variable to 0.
• During the insertion and deletion operation, we increment and decrement the size by 1 respectively.
• Therefore, at any moment the size variable contains the correct size of the HashMap. Thus, in the size() function, we just return the value of the size variable.

Implementation of size()

public int size() {
	return size;  // return the value of size variable
}

Display elements of hashmap

We are using the display() function to display all the key-value pairs of the hashmap. 

Implementation of display()

public void display() {  // Function to display all the key value pairs in the 
                        // hashMap
      System.out.println("Display Begins");
      for (int bi = 0; bi < buckets.length; bi++) {  // iterate through all the
 // buckets
        System.out.print("Bucket " + bi + " ");
        for (Node node : buckets[bi]) {  // for any bucket bi, iterate through
// all the nodes in it and print the key and value corresponding to it
          System.out.print( node.key + " -> " + node.value + " ");
        }
        System.out.println(".");
      }
      System.out.println("Display Ends");
  }
}

You can also read about the Longest Consecutive Sequence.

Implementation Code of Hashmap in Java

The complete program with all the above four operations is as follows 

import java.io.*;
import java.util.*;

public class Main {

  public static class HashMap<K, V> {
    private class Node{
      K key;
      V value;

      HMNode(K key, V value) {
        this.key = key;
        this.value = value;
      }
    }

    private int size; // n
    private LinkedList<HMNode>[] buckets; // N = buckets.length

    public HashMap() {
      initbuckets(4);
      size = 0;
    }

    private void initbuckets(int N) {
      buckets = new LinkedList[N];
      for (int bi = 0; bi < buckets.length; bi++) {
        buckets[bi] = new LinkedList<>();
      }
    }

    public void put(K key, V value) throws Exception {
      int bi = hashfn(key);
      int di = getIndexWithinBucket(key,bi);
      if(di!=-1){
          Node node = buckets[bi].get(di);
          node.value = value;
      }
      else{
          Node node = new HMNode(key,value);
          buckets[bi].add(node);
          size++;
      }
    }
    
    private int hashfn(K key){
        int hc = key.hashCode();
        return Math.abs(hc)%buckets.length;
    }
    
    private int getIndexWithinBucket(K key, int bi){
        int di = 0;
        for(Node node : buckets[bi]){
            if(node.key.equals(key)){
                return di;
            }
            di++;
        }
        return -1;
    }

    public V get(K key) throws Exception {
      int bi = hashfn(key);
      int di = getIndexWithinBucket(key,bi);
      if(di!=-1){
          Node node = buckets[bi].get(di);
          return node.value;
      }
      else{
          return null;
      }
    }

    public boolean containsKey(K key) {
      int bi = hashfn(key);
      int di = getIndexWithinBucket(key,bi);
      if(di!=-1){
          return true;
      }
      else{
          return false;
      }
    }

    public V remove(K key) throws Exception {
      int bi = hashfn(key);
      int di = getIndexWithinBucket(key,bi);
      if(di!=-1){
          Node node = buckets[bi].remove(di);
          size--;
          return node.value;
      }
      else{
          return null;
      }
    }

    public ArrayList<K> keyset() throws Exception {
      ArrayList<K> keys = new ArrayList<>();
      for(int bi =0;bi<buckets.length;bi++){
          for(Node node:buckets[bi]){
              keys.add(node.key);
          }
      }
      return keys;
    }

    public int size() {
      return size;
    }

  public void display() {
      System.out.println("Display Begins");
      for (int bi = 0; bi < buckets.length; bi++) {
        System.out.print("Bucket " + bi + " ");
        for (Node node : buckets[bi]) {
          System.out.print( node.key + " -> " + node.value + " ");
        }
        System.out.println(".");
      }
      System.out.println("Display Ends");
  }
}

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    HashMap<String, Integer> map = new HashMap();

    String str = br.readLine();
    while (str.equals("quit") == false) {
      if (str.startsWith("put")) {
        String[] parts = str.split(" ");
        String key = parts[1];
        Integer val = Integer.parseInt(parts[2]);
        map.put(key, val);
      } else if (str.startsWith("get")) {
        String[] parts = str.split(" ");
        String key = parts[1];
        System.out.println(map.get(key));
      } else if (str.startsWith("containsKey")) {
        String[] parts = str.split(" ");
        String key = parts[1];
        System.out.println(map.containsKey(key));
      } else if (str.startsWith("remove")) {
        String[] parts = str.split(" ");
        String key = parts[1];
        System.out.println(map.remove(key));
      } else if (str.startsWith("size")) {
        System.out.println(map.size());
      } else if (str.startsWith("keyset")) {
        System.out.println(map.keyset());
      } else if (str.startsWith("display")) {
        map.display();
      }
      str = br.readLine();
    }
  }
}

Input

put India 135
put Aus 5
put Canada 3
display
get China
remove Aus
get Aus
containsKey US
put US 10
put UK 20
remove US
containsKey US
put Pak 80
put China 200
display
put India 138
display
quit

Output

Display Begins
Bucket 0 .
Bucket 1 .
Bucket 2 Canada -> 3 .
Bucket 3 India -> 135 Aus -> 5 .
Display Ends
null
5
null
false
10
false
Display Begins
Bucket 0 .
Bucket 1 .
Bucket 2 Canada -> 3 UK -> 20 Pak -> 80 .
Bucket 3 India -> 135 China -> 200 .
Display Ends
Display Begins
Bucket 0 .
Bucket 1 .
Bucket 2 Canada -> 3 UK -> 20 Pak -> 80 .
Bucket 3 India -> 138 China -> 200 .
Display Ends

Complexity Analysis

Time Complexity

Generally, the time complexity is O(1) but in case there are a lot of collisions, the time complexity can go up to O(n) in the worst case.

Reason: Finding, retrieving, and deleting elements from the linked list at an index takes O(1) time. But in case of collision, you have to travel the whole linked list through, and then it would be O(n)  where n is the size of the largest linked list.

Space Complexity

The space complexity of this approach is O(n), where n is the number of key-value pairs.

Reason: Only space that is needed here is to store the key-value pairs. 

Check out this problem - Pair Sum In Array.

Still didn’t completely understand the implementation? Watch this video for a crystal clear understanding.

Frequently Asked Questions

What is the internal working of HashMap?

The Java collection framework includes HashMap. It employs a method known as Hashing. It is responsible for implementing the map interface. It saves the data in the Key/Value pair. HashMap has an array of nodes, and each node is represented by a class. Internally, it stores Key and Value in an array and LinkedList data structure.

How HashMap are implemented in Java?

We use a HashMap in Java using the Hashmap class in Java. HashMap<K, V> is a part of Java’s collection and is found in java.util package. It implements the Java Map interface in its most basic form. It keeps data in (Key, Value) pairs.

What is the internal representation of HashMap?

The internal representation of HashMap in Java consists of an array of buckets, where each bucket is a linked list of key-value pairs. The array size is initially determined by the capacity parameter, and the load factor determines when the HashMap needs to resize.

What is the difference between internal working of HashMap and HashTable?

The main difference between the internal working of HashMap and HashTable is that HashMap allows null keys and values, is not synchronized and has better performance. HashTable does not allow null keys or values and is synchronized for thread-safety.

Conclusion

HashMap is a very efficient data structure because of its constant i.e. O(1) insertion, deletion, and searching time complexity. This article describes how to Implement a hashmap in Java, but it should not be the end of your practice.

Understanding how to use hashmaps can be extremely beneficial because hashmap-related questions, such as Pair sum, Check duplicate, Count distinct substrings, Maximum frequency number, and many more. 

Problems with this topic are frequently asked during various coding contests and placement tests. To practice more such problems, CodeStudio is a one-stop destination. 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on  CodeStudio.

Happy Coding!