HashMap internally works in Java

HashMap internally works in Java

1. Hashing Mechanism

   Explanation: HashMap uses a hashing technique to store key-value pairs. When you add a key-value pair to a HashMap, the key is hashed to determine the index (or bucket) where the value will be stored. This hashing process involves calculating a hash code for the key using the hashCode() method.

2. Bucket Structure

   Explanation: Internally, Its is implemented as an array of Node objects (or Entry objects in older implementations). Each Node contains the key, value, and a reference to the next Node in case of hash collisions (when multiple keys hash to the same index).

3. Handling Collisions

   Explanation: If two keys hash to the same index (collision), HashMap uses a linked list (or a tree in Java 8+ for large collisions) to store multiple entries in the same bucket. This ensures that all entries with the same hash code are accessible.

4. Capacity and Load Factor

   Explanation: HashMap has an initial capacity and a load factor (0.75 by default). As entries are added, if the size exceeds the product of the capacity and load factor, the is resized to maintain efficiency. Resizing involves rehashing all entries to distribute them across a larger array of buckets.

HashMap

Example in Java

Let’s demonstrate how works internally with a simple Java example:

java
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // Creating a HashMap
        Map<String, Integer> studentScores = new HashMap<>();

        // Adding key-value pairs
        studentScores.put("Alice", 95);
        studentScores.put("Bob", 85);
        studentScores.put("Carol", 90);

        // Accessing elements
        System.out.println("Alice's score: " + studentScores.get("Alice"));

        // Iterating over HashMap (buckets)
        for (int i = 0; i < studentScores.size(); i++) {
            System.out.println("Bucket " + i + ": ");
            studentScores.forEach((key, value) -> {
                if (Objects.hash(key) % studentScores.size() == i)
                    System.out.println(key + " -> " + value);
            });
        }

        // Removing a key
        studentScores.remove("Bob");

        // Checking existence of a key
        if (studentScores.containsKey("Bob")) {
            System.out.println("Bob's score: " + studentScores.get("Bob"));
        } else {
            System.out.println("Bob's score not found.");
        }

        // Size of HashMap
        System.out.println("Number of students: " + studentScores.size());
    }
}

Explanation: In this example:

  • Hash Map stores key-value pairs (“Alice” -> 95, “Bob” -> 85, “Carol” -> 90) internally based on their hash codes.
  • get() method retrieves values based on the hashed index of the key (studentScores.get(“Alice”)).
  • Iteration over Hash Map shows how entries are grouped into buckets based on their hash codes.
  • remove() method removes a key-value pair (studentScores.remove(“Bob”)), adjusting the internal structure if necessary.
  • size() method returns the number of key-value pairs currently stored.

Homepage

Readmore