HashMap internal working in java

HashMap:

HashMap in java is represents a collection type which can contains the objects/elements in key-value pair form. It extends AbstractMap class and implements the Map interface. It not maintains any order for its elements. It not allowed duplicate values as key. It can have only one null key and multiple null values. HashMap uses array and LinkedList data structure to store objects, in the form of array of nodes.

Node representation in HashMap

Hashing

Hashing refers to a mechanism to assign a unique code or value for any object or variable by applying any specific algorithm on its properties.

HashMap Entry class

static class Entry implements Map.Entry
{
    final K key;
    V value;
    Entry next;
    final int hash;
    //Other code statements
}

Code syntax:

 
Map hashMap = new HashMap<>();

When we create a HashMap, it will create following structure with default load factor 0.75.

When we add first element in HashMap, an array of size 16 will be created and assign to table element. Array elements are known as buckets here i.e. A bucket represents an element of HashMap array. Every bucket is used to store nodes which represents a HashMap.Entry class object with 4 fields (int hash, K key, V value, Node next).

Note: Two or more nodes can have the same bucket.

Let’s discuss important terms here.

Capacity: No. of buckets in the HashMap (16 by default).
Load factor: represents a factor in HashMap which calculates when rehashing will be done. Rehashing is the process of increasing the size (no. of buckets) of HashMap. As we discussed earlier that default capacity will be 16 and load factor will be .75. Threshold will be calculated based on the capacity and load factor (capacity * load factor) i.e. 16 * .75 = 12. So, capacity of the HashMap will be multiply by 2 whenever threshold reached.

How put and get works in HashMap

package com.w3schools;

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

public class Test {
	public static void main(String args[]){		
		Site site1 = new Site("w3schools", 1);
		Site site2 = new Site("java", 2);
		Site site3 = new Site("spring", 1);
		
		Map hashMap = new HashMap<>();
		hashMap.put(site1, "First site");
		hashMap.put(site2, "Second site");
		hashMap.put(site2, "Third site");
		hashMap.put(site3, "Fourth site");
		System.out.println("HashMap Elements: " + hashMap);
		
		System.out.println("site1: " + hashMap.get(site1));
		System.out.println("site2: " + hashMap.get(site2));
		System.out.println("site3: " + hashMap.get(site3));
	}
}

class Site{
	private String name;
	private int id;
	
	public Site(String name, int id) {
		super();
		this.name = name;
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}
	
	@Override
	public String toString() {
		return this.getId() + "-" + this.getName();
	}

	@Override
	public int hashCode() {
		//For simplicity we are returning id as hashCode value 
		return this.id;
	}
	
	@Override
	public boolean equals(final Object obj) {
		if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Site siteObject = (Site) obj;
        if(this.getName() == siteObject.getName() && 
        		this.getId() == siteObject.getId())
        	return true; 
        else
        	return false;
	}	
}

Output

HashMap Elements: {1-w3schools=First site, 1-spring=Fourth site, 2-java=Third site}
site1: First site
site2: Third site
site3: Fourth site

Index calculation in HashMap:
The hashCode() method returns a hash code value (an integer number) for the object which represents the memory address of the object. It may return a value from the range of integer. But if we create an array with this range, then it may result into OutOfMemoryException. Index value is generated to minimize the size of array. Index is calculated with following expression.

index = hashCode(key) & (n-1)

Where n represents the number of buckets.

Note: Normally, the bucket id is hash code / no of buckets

HashMap insertion in java (HashMap put method):
When an element is inserted into HashMap using put method, index value is calculated first. The object will be placed at index value if no other object is present at that index. Let us understand with above example. Let us look at the statement hashMap.put(site1, “First site”);. Element is inserted at index 1 with following details as there was no element at index 1.

Now, when second put operation is performed i.e. the statement hashMap.put(site2, “Second site”); executes. The index will be calculated again and it will return 2. As there is no element at index 2 so second element will be inserted at index 2.

Now, let us see what happens if we executes third insert statement i.e. hashMap.put(site2, “Third site”);. The index value will be calculated and it will again return 2. Collision occurs here in the HashMap as element is already exist at index 2. Collision is resolved based on key value. If key is also same then already existing element will be replaced by new one otherwise the next field of already existing element will now point to the new node element which results into a linked list. For third statement key will also be same and that’s why already existing element will be replaced.

Now, let us discuss the second case of HashMap collision in which key will be different. We are executing fourth statement here hashMap.put(site3, “Fourth site”);. The index value will be calculated and it will again return 1. Collision occurs here in the HashMap as element is already exist at index 1. Collision is resolved based on key value. Key is different here from the key of already existing element at index 1 and that’s why as discussed earlier the next field of already existing element will now point to the new node element which results into a linked list.

HashMap reading in java (HashMap get method):
We will use get() method to read the value of an element from HashMap. Index value is calculated first when get method is called with the specified key. Key will be compared to the key of the element at the calculated index value. If key matched is found then value of the element will be return otherwise next field of the element will be checked and if it is not null then key will be compared again with the key of next element and if key matched is found then value of the element will be return otherwise so on until next refers to null.

Another important and related topic: HashCode and Equals method contract

HashMap improvements in Java 8

As we discussed above that when a hash collision occurs entry objects are stored as a node in a Linked List. Now, here comes the situation of finding the correct key with in a Linked List. As we know that random access is not allowed for Linked List and that’s why in a worst case scenario the complexity will be O(n).
To resolve this issue, Java 8 comes with an improvement which is, after a certain threshold the hash elements will use balanced tree instead of linked list. Which results into performance improvement from O(n) to O(log n) in the worst case scenario.

Current threshold for converting hash elements structure (in case when bucket becomes too large, due to insertion of elements) from linked list to balanced tree is 8 (TREEIFY_THRESHOLD = 8) whereas threshold for converting hash elements structure (in case when bucket becomes too small, due to removal of elements) from balanced tree to linked list is 6 (UNTREEIFY_THRESHOLD = 6)