What Is HashMap In Java and How It Works Internally

While working with Java, understanding data is crucial for writing efficiently, effective. Among these structures, the HashMap stands out as a powerful utility that provides fast data retrieval Whether you're a novice learning the ropes or an experienced developer seeking to refresh your knowledge, diving into the inner workings of HashMap can enrich your programming skills. This article will explore what a HashMap is, how it functions internally, and why it is so widely used in Java applications.

What is HashMap?

A HashMap is a part of the Java Collections Framework and implements the Map interface. It stores data in key-value pairs, allowing for efficient data retrieval through keys. The beauty of a HashMap is that it provides quick lookups, insertions, and deletions, which makes it incredibly useful in various programming situations.

Points To Remember About HashMap

Key-Value Pair Storage: Every entry in a HashMap consists of a key and its associated value. Each key must be unique, but multiple keys can map to the same value.

Null Values: HashMap allows for one null key and multiple null values, making it flexible in certain use cases.

Non-Synchronized: HashMap is not synchronized it simply means it is not thread-safe. If multiple threads are accessing a HashMap concurrently, it may lead to unpredictable results, we need to handle it properly.

How Does HashMap Work Internally?

To truly appreciate the power of HashMap, we need to delve into its internal workings. At its core, a HashMap uses a combination of arrays and linked lists to store data.

The Hash Function

The HashMap uses a hash function to compute an index based on the key. As follows:

1. Hashing the Key: The key's hash code is computed using the hashCode() method, which returns an integer value.

2. Calculating the Bucket Index: The hash code is then transformed into an index using the formula `index = hashCode & (arrayLength-1)`, where `arrayLength` is the length of the internal array which is 16 by default.

3. Storing the Value: The entry (key-value pair) is stored at the calculated index in an array.

Handling Collisions

HashMap needs to handle scenarios where two keys produce the same index, known as a collision. Java uses a strategy called "chaining," where each slot in the array contains a linked list. If a collision occurs, the new entry is added to this list.

Here’s how collision resolution works:

If multiple keys hash to the same index:
A linked list is created at that index.
All colliding entries are stored in this linked list.
When retrieving a value, the linked list is traversed to find the corresponding key.

Update Java 1.8

From Java 1.8, to improve the performance HashMap converts a LinkedList into a red-black tree if hash collisions occur multiple times and the LinkedList reaches its limit, which is 8 by default.

Resizing the HashMap

One critical aspect of the HashMap is its dynamic resizing. When the number of entries exceeds a predefined threshold, known as the load factor (commonly set to 0.75), the HashMap automatically increases its size. This is achieved through:

Doubling the Size of the Array: The capacity of the internal array is doubled.
Rehashing: All existing entries are rehashed to fit into the new array. This can be an expensive operation, so it is best to consider the initial capacity when creating a HashMap.

Performance

The performance of a HashMap can be summarized as follows:

Average Case: O(1) for get, put, and remove operations, thanks to efficient hashing.

Worst Case: O(n) when collisions occur frequently, causing many entries to be in linked lists.

Practical Use Cases for HashMap

HashMaps are versatile structures used in many applications. Here are some common use cases:

Caching: Storing temporary data for quick access.

Counting Frequencies: Tallying occurrences of items in a collection (e.g., counting how many times a word appears in text).

Lookups: Storing configuration settings or user preferences for rapid retrieval.

Simple Example of a HashMap:

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // Create a HashMap to store the names of employees and their IDs
        HashMap employeeMap = new HashMap<>();

        // Add some entries to the HashMap
        employeeMap.put("Ravi", 101);
        employeeMap.put("Rocky", 102);
        employeeMap.put("Akash", 103);

        // Retrieve and print values from the HashMap
        System.out.println("ID of Rocky: " + employeeMap.get("Rocky"));
        System.out.println("ID of Akash: " + employeeMap.get("Akash"));

        // Check if a key exists in the HashMap
        if (employeeMap.containsKey("Rocky")) {
            System.out.println("Rocky is in the map with ID: " + employeeMap.get("Rocky"));
        }

        // Iterate over the HashMap entries
        for (String name : employeeMap.keySet()) {
            System.out.println("Employee Name: " + name + ", ID: " + employeeMap.get(name));
        }
    }
}

OUTPUT

ID of Rocky: 102

ID of Akash: 103

Rocky is in the map with ID: 102

Employee Name: Ravi, ID: 101

Employee Name: Rocky, ID: 102

Employee Name: Akash, ID: 103

In conclusion, HashMap is an essential data structure in Java that provides efficient storage and retrieval of data in key-value pairs. Its internal mechanisms, including hashing, collision resolution, and dynamic resizing, allow for high performance in diverse scenarios. Understanding how HashMap works can vastly improve your coding efficiency and help you write better, more maintainable code.

Happy Coding... :)

Menu

Aug 9, 2024