Skip to content
  • Facebook
GeekCer Logo

GeekCer

The geek's Coding education and Review centre

  • Home
  • Tutorials
    • Java
    • Servlet
    • JSP
    • Python
    • C Tutorial
    • Spring
    • Spring Boot
    • MongoDB
    • Hibernate
    • Data Structure
  • General Knowledge
  • Biography
  • Grammar
  • Festival (त्योहार)
  • Interview
  • Differences
  • Important
  • Toggle search form

Home » Java » Internal Working of HashMap in Java, Rehashing, Collision

  • What is Tense in Hindi (काल क्या है)?
    What is Tense in Hindi (काल क्या है)? Grammar
  • Bhagat Singh Biography in Hindi (भगत सिंह का जीवन परिचय)
    Bhagat Singh Biography in Hindi (भगत सिंह का जीवन परिचय) Biography
  • Indian Navy Day
    Indian Navy Day: जल सेना दिवस कब और क्यों मनाया जाता है? General Knowledge
  • Sunder Kand in Hindi | Hanuman Kand | हनुमान जी का सुंदरकांड
    Sunder Kand in Hindi | Hanuman Kand | हनुमान जी का सुंदरकांड Spiritual
  • Farmers Day
    National Farmers Day in Hindi | राष्ट्रीय किसान दिवस पर निबंध | चौधरी चरण सिंह जयंती General Knowledge
  • State the Universal law of gravitation | Law of Gravity, Formula
    State the Universal law of gravitation | Law of Gravity, Formula Science
  • Unicef day
    Unicef day is celebrated on December 11 | Speech on unicef day General Knowledge
  • Lanka Kand Summary in Hindi | Ram Vs Ravana | लंका काण्ड
    Lanka Kand Summary in Hindi | Ram Vs Ravana | लंका काण्ड Spiritual

Internal Working of HashMap in Java, Rehashing, Collision

Posted on June 18, 2022June 18, 2022 By GeekCer Education No Comments on Internal Working of HashMap in Java, Rehashing, Collision
Internal Working of HashMap in Java | Rehashing , Hash Collision

Learn about HashMap internal working, Hashing, Re-Hashing, Node usage in HashMap, and Node structure in Java.

Table of Contents

  • HashMap node structure
  • How does HashMap work internally in Java?
  • Bucket Index calculation in HashMap
  • HashMap Hash collision in java
  • What is rehashing in HashMap?
  • What is Java 8 improvement in HashMap internal working?
  • What if two different keys have the same hashcode?

HashMap node structure

To define the map’s entries, HashMap uses the Node<K,V> class, which is a static inner class. It is not incorrect to state that each element in the HashMap is a node.


static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;		
		....
}

How does HashMap work internally in Java?

What is Bucket? Multiple key-value pairs can be stored in a bucket. Bucket uses a simple linked list to store objects in HashMap. HashMap uses multiple buckets, each bucket in HashMap refers to a singly linked list of nodes.

You may have the basic idea about the hash function and hashCode. HashMap internally uses the hashCode of the object that we add and then the hash function uses this hashCode. Hash function finds the index by using hashCode and at that index the new entry is added.

Hash function finds the index and checks if the key is already available with the same hashCode in the bucket. If the hashCode matches, the keys are equalized using the equals() method. If equals() returns true, the value of that key in the node is overwritten; otherwise, a new node is created and added to the bucket’s singly linked list.

If the key is not available with the same hashCode in the bucket, the new node is added to the identified bucket.

Bucket Index calculation in HashMap

For each operation, such as store, retrieve, and so on, the HashMap creates a bucket index. The key object is used to calculate the bucket index when we save or retrieve an entry in the HashMap.

Bucket index plays a very important role in the internal working of the HashMap operation. Let’s look at the following formula for bucket index creation.

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

By using above formula index value is generated, and HashMap uses it to locate the bucket .In the this formula n is the size of the array or bucket size.

HashMap used (n-1) to handle ArrayOutOfBoundsException in the calculation above. Because an ArrayOutOfBoundsException is raised if the generated hash value exceeds the array’s size, (n-1) reduces the index value and is always between 0 and (n-1).

The following is an example program for bucket index generation.

Disclaimer: This program (BucketIndexGeneration.java) is designed to demonstrate how the Bucket Index is created. Java may not generate the bucket index in the same manner. This is only to help the user understand how Bucket Index works.


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

public class BucketIndexGeneration {
	private static final int DEFAULT_INITIAL_HASH_MAP_SIZE = 16;

	public static void main(String[] args) {
		Map<String, Integer> marksMap = new HashMap<>(DEFAULT_INITIAL_HASH_MAP_SIZE);

		String key1 = "Java";
		marksMap.put(key1, 75);
		int hash1 = key1.hashCode();
		int index1 = bucketIndex(hash1);
		System.out.println("Entry 1: HashCode: " + hash1 + "  Bucket Index : " + index1);

		String key2 = "Database";
		marksMap.put(key2, 70);
		int hash2 = key2.hashCode();
		int index2 = bucketIndex(hash2);
		System.out.println("Entry 2: HashCode: " + hash2 + "  Bucket Index : " + index2);

		String key3 = "HTML";
		marksMap.put(key3, 85);
		int hash3 = key3.hashCode();
		int index3 = bucketIndex(hash3);
		System.out.println("Entry 3: HashCode: " + hash3 + "  Bucket Index : " + index3);

		String key4 = "C#";
		marksMap.put(key4, 80);
		int hash4 = key4.hashCode();
		int index4 = bucketIndex(hash4);
		System.out.println("Entry 4: HashCode: " + hash4 + "  Bucket Index : " + index4);
	}

	static final int bucketIndex(int hash) {
		return (DEFAULT_INITIAL_HASH_MAP_SIZE - 1) & hash;
	}
}

Entry 1: HashCode: 2301506  Bucket Index : 2
Entry 2: HashCode: 1854109083  Bucket Index : 11
Entry 3: HashCode: 2228139  Bucket Index : 11
Entry 4: HashCode: 2112  Bucket Index : 0

How does HashMap calculate bucket index internally in Java?

Bucket Index calculation in HashMap
Bucket Index calculation in HashMap

HashMap Hash collision in java

How do hash collisions happen and how are they resolved? When the hash function returns the same bucket location for two different keys, collisions occur. In other words, hash collision is a situation where the calculated bucket index of the two keys is the same.

The bucket index of Entry 2 and Entry 3 is the same in the above program and image, which is 11.

In this scenario, HashMap uses the equals() method to determine whether the keys are equal. If the current key and the previous key are same the previous value is replaced with the current value.

If the keys are not the same then connects the node to the existing node . As a result, index 11 will be used to hold both node (Entry 2 and Entry 3).

What is rehashing in HashMap?

The process of re-calculating the hash code of previously stored items is known as rehashing. When the items in the map (bucket array) surpasses the threshold value, a new size of bucket array is created with a capacity that is about twice as large.

Rehashing is a concept that is completely dependent on the threshold value of the HashMap.

threshold = capacity * (load factor of 0.75).
Load Factor of HashMap: 0.75
Default Initial Capacity: 16
Threshold Value = Load Factor of HashMap * Default Initial Capacity 
Theshhold Value = 0.75 * 16 = 12

When the hash map receives the 13th key-value pair, the size of the bucket array is increased
New Capacity: 16*2 = 32.

Theshhold Value = Load Factor * New Capacity 
Theshhold Value = 0.75 * 32 = 24

What is Java 8 improvement in HashMap internal working?

As we know, singly-linked lists were used to store nodes. But this is before Java 8. But after Java 8, some modifications have been made to the HashMap implementation to improve performance.

When the number of items in a hash bucket reaches a specific threshold, bucket switches from linked list to balanced tree.

static final int TREEIFY_THRESHOLD = 8;

What if two different keys have the same hashcode?

If the hashcode of two different objects is same then equals() method is used to compare both the objects.


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

public class BucketIndexGeneration {
	private static final int DEFAULT_INITIAL_HASH_MAP_SIZE = 16;

	public static void main(String[] args) {
		Map<String, Integer> marksMap = new HashMap<>(DEFAULT_INITIAL_HASH_MAP_SIZE);

		String key = "Angular";
		marksMap.put(key, 80);
		int hash = key.hashCode();
		int index = bucketIndex(hash);
		System.out.println("Entry 1: HashCode: " + hash + "  Bucket Index : " + index);

		key = "Angular";
		marksMap.put(key, 78);
		hash = key.hashCode();
		index = bucketIndex(hash);
		System.out.println("Entry 2: HashCode: " + hash + "  Bucket Index : " + index);

		System.out.println(marksMap);

		System.out.println(marksMap);

	}

	static final int bucketIndex(int hash) {
		return (DEFAULT_INITIAL_HASH_MAP_SIZE - 1) & hash;
	}
}

Entry 1: HashCode: 806118850  Bucket Index : 2
Entry 2: HashCode: 806118850  Bucket Index : 2
{Angular=78}

You can see that Entry 1 and Entry 2 have the same HashCode in the example above. In this situation, HashMap uses equals() methods internally, and if both keys are still the same, the previous value is replaced with the current value.

The map has only one entry. The value 80 is replaced by the value 78.

Recommended Articles

  • Java 8 interview questions
  • Java stream collect to map example
  • Sequential Vs Parallel stream
  • Concurrent collection with examples in java
  • Example of Comparable vs Comparator

Share this:

  • Click to share on Facebook (Opens in new window)
  • Click to share on WhatsApp (Opens in new window)
  • Click to share on Twitter (Opens in new window)
  • More
  • Click to share on LinkedIn (Opens in new window)
  • Click to share on Pinterest (Opens in new window)

Also Read

Java Tags:How HashMap works in Java Internally, Role of hashCode() and equals() methods in HashMap

Post navigation

Previous Post: Sequential and Parallel Stream in Java | Example, Differences

More Related Articles

JDBC Driver in Java JDBC Driver in Java Java
Difference between final, finally and finalize Difference between final, finally and finalize Differences
Fork/Join Framework in Java | RecursiveTask, RecursiveAction Fork/Join Framework in Java | RecursiveTask, RecursiveAction Java
Java If-else Statement Java If-else Statement Java
Concurrent collections in Java, details, advantages, examples Concurrent collections in Java, details, advantages, examples Java
Java 8 interview questions and answers, Java Stream, Optional Java 8 interview questions and answers, Java Stream, Optional Important

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

  • National Farmers Day in Hindi | राष्ट्रीय किसान दिवस पर निबंध | चौधरी चरण सिंह जयंती
  • Human rights day in Hindi: 10 दिसंबर ह्यूमन राइट्स डे
  • Unicef day is celebrated on December 11 | Speech on unicef day
  • Indian Navy Day: जल सेना दिवस कब और क्यों मनाया जाता है?
  • P V Sindhu Biography in Hindi, Badminton, State, Caste पी. वी. सिंधु जीवन परिचय, कहानी, राज्य, जाति
  • Draupadi Murmu Biography In Hindi | द्रौपदी मुर्मू की जीवनी
  • Difference between Internet and Intranet
    Difference between Internet and Intranet Differences
  • Network kya hai (नेटवर्क क्या है)
    Network kya hai (नेटवर्क क्या है) Networking
  • TCP/IP Model, Full Form, Layers and their Functions
    TCP/IP Model, Full Form, Layers and their Functions Networking
  • Similarities and difference between OSI and TCP/IP model
    OSI vs TCP/IP Model, Similarities and difference between OSI and TCP/IP model Networking
  • OSI Model | 7 Layers of OSI Model in Computer network
    OSI Model | 7 Layers of OSI Model in Computer network, Functions Networking
  • IPv4 Vs IPv6 | Difference between IPv4 and IPv6
    IPv4 Vs IPv6 | Difference between IPv4 and IPv6 Differences
  • Difference between TCP and UDP
    Difference between TCP and UDP | TCP vs UDP examples Differences
  • Java Tutorial
  • Servlet Tutorial
  • JSP Tutorial
  • Maven Tutorial
  • HTML Tutorial
  • Programs
  • Hindi/English Grammar
  • Difference Between ... and ...
  • HR Interview
  • Important Articles

Write to Us:
geekcer.code@gmail.com

  • About Us
  • Privacy and Policy
  • Disclaimer
  • Contact Us
  • Sitemap

Copyright © GeekCer 2022 All Rights reserved