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.
Table of Contents
Example in Java
Let’s demonstrate how works internally with a simple Java example:
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.