CodesJava

Easy learning with example program codes

how hashmap works internally in java?


HashMap:

HashMap extends AbstractMap class and implements the Map interface. It contains the elements in key-value pair form. It not maintains any order for its elements. It not allowed duplicate key. A HashMap can have only one null key and multiple null values.

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

 
Map hashMap = new HashMap<>();

HashMap internal working 1

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.

HashMap internal working 1

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.codesjava;
 
import java.util.HashMap;
import java.util.Map;
 
public class Test {
	public static void main(String args[]){		
		Site site1 = new Site("codesjava", 1);
		Site site2 = new Site("java", 2);
		Site site3 = new Site("spring", 1);
 
		Map<Site, String> 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-codesjava=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.

HashMap Internal Working

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.

HashMap Internal Working

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.

HashMap Internal Working

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 Internal Working

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.

Related Topics

Posted in Java   

Core Java Tutorial

Programming language overview.
Overview of Java.
Java features
JVM architecture details.
JVM, JRE and JDK.
Java Coding Guidelines.
Some important definitions.
Variable and data types.
Hello world java program.
Core java examples programs.
Important Java Programs.
How to set permanent path in java?
OOPs Basics.
Object and Class in Java.
OOPs Principles/Concepts.
Abstraction in java.
Encapsulation in java.
Polymorphism in java.
Method overloading in java.
Method overriding in java.
Dynamic method dispatch.
Runtime polymorphism.
Association in java.
Inheritance in java.
Aggregation in java.
Command line arguments in java.
Command line argument program in eclipse.
Read input from command line using Scanner.
Java array programs
Java star pattern programs
Java number pattern programs
final in java.
Abstract class in java.
Interface in java.
Custom marker Interface in java.
Constructor in java.
Package in java.
Access modifier in java.
Static import in java.
Package class in java.
this in java.
Instance initialize block.
Anonymous block.
super in java.
Static in java.
final in java.
Java cloning deep and shallow
Shallow vs Clone copy
String handling in java.
String handling programs.
StringBuffer in java.
StringBuilder in java.
Exception Handling Tutorial.
Multithreading Tutoial.
Java input output stream tutorial.
Collections framework in java tutorial.
Collections framework programs.
Java Random class
Java annotations.
Java design principles.
Java 7 features
Java 8 features
Java networking tutorial
Java Reflection tutorial


Industrial Training

We offers Placement Oriented Training on Java, Spring, JSF, Hibernate, PHP, AngularJS, Angular 4, PLSQL, Oracle BI Publisher etc. We also provides Online training, please mail us at hr@codesjava.com.

Development

We also provides the Development services for Website Development , Java Development, PHP Development, Android App Development etc. You can contact us on hr@codesjava.com.

Copyright © 2019 CodesJava DMCA.com Protection Status SiteMap Reference: Java Wiki