Internal Working of HashMap in Java

Posted on: February 8, 2025 Posted by: rahulgite Comments: 0

Introduction

A HashMap in Java is a part of the java.util package and is used to store key-value pairs. It provides fast lookups, insertions, and deletions with an average time complexity of O(1). It internally uses a hashing mechanism to map keys to values efficiently.

1. Data Structure Used

HashMap is implemented using an array of linked lists (or Red-Black Trees for optimization in Java 8+). Each bucket in the array holds a linked list of key-value pairs.

Implementation in Java:

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

When a HashMap is created, it initializes an array:

transient Node<K,V>[] table;

2. How Elements are Stored

When a key-value pair is inserted into a HashMap, the following happens:

  1. Hashing: The hashCode() of the key is computed and used to determine the bucket index.
  2. Index Calculation: The index is computed as: int index = (hash & (table.length - 1));
  3. Insertion:
    • If the bucket is empty, the key-value pair is inserted.
    • If a collision occurs (same index for multiple keys), Java uses separate chaining (linked list or tree).
    • In Java 8+, if the bucket size exceeds 8 entries, the linked list converts into a Red-Black Tree for improved efficiency.

Example:

HashMap<String, Integer> map = new HashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);

3. Red-Black Tree and Its Role in HashMap

In Java 8 and later, when a bucket contains more than 8 nodes, the linked list structure is converted into a Red-Black Tree to improve performance.

Why Red-Black Tree?

  • Faster lookup: Linked list lookup time is O(n), but Red-Black Tree lookup time is O(log n).
  • Balanced structure: Red-Black Trees ensure that the tree remains balanced, reducing the worst-case complexity.
  • Efficient insertion/deletion: Operations like insert, delete, and search run in O(log n) time, making it more efficient for large datasets.

How It Works in HashMap

  1. When the number of elements in a single bucket exceeds 8, Java converts the linked list into a Red-Black Tree.
  2. When elements are removed and the bucket size drops below 6, it converts back into a linked list.
  3. Performance Benefits: Instead of a worst-case O(n) lookup in a linked list, the lookup time in a Red-Black Tree is reduced to O(log n).

Example Scenario:

HashMap<Integer, String> map = new HashMap<>();
for (int i = 1; i <= 20; i++) {
    map.put(i, "Value" + i);
}

If too many elements collide and hash to the same bucket, Java converts the bucket’s linked list into a Red-Black Tree for faster retrieval.

4. Accessing Elements from HashMap

To retrieve a value from a HashMap, the get() method is used. It follows these steps:

  1. Computes the hashCode() of the given key.
  2. Finds the appropriate bucket index.
  3. If multiple entries exist in the bucket (collision case), it iterates through the linked list or Red-Black Tree.
  4. If the key matches (via equals()), the corresponding value is returned.

Example:

HashMap<String, Integer> map = new HashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
System.out.println(map.get("Apple")); // Output: 1
System.out.println(map.get("Banana")); // Output: 2

If a key does not exist, get() returns null.

System.out.println(map.get("Orange")); // Output: null

5. What Happens When a Duplicate Key is Added?

If the same key is added again:

  1. The hashCode() of the key is computed and the correct bucket is found.
  2. The equals() method is called to check if the key is already present.
  3. If the key exists, the old value is replaced with the new one.

Example:

HashMap<String, Integer> map = new HashMap<>();
map.put("Apple", 1);
map.put("Apple", 2); // Replaces previous value
System.out.println(map.get("Apple")); // Output: 2

6. Collision Handling in HashMap

Collisions occur when two different keys hash to the same index. Java handles collisions using separate chaining:

  1. Linked List (Java 7 and earlier): Keys with the same index form a linked list.
  2. Red-Black Tree (Java 8+): If the linked list grows beyond 8 entries, it converts into a Red-Black Tree for faster lookups.

7. Load Factor and Resizing

  • The default load factor is 0.75, meaning when the number of elements exceeds 75% of the capacity, the HashMap resizes (doubles in size) and rehashes all elements.
  • This prevents excessive collisions and maintains efficiency.

Key Takeaways

✔ HashMap provides fast lookups, insertions, and deletions (O(1)).

✔ It uses hashing to compute the bucket index.

✔ Uses separate chaining (linked list or Red-Black Tree) to handle collisions.

✔ When a duplicate key is added, HashMap.put() replaces the old value.

✔ Red-Black Trees improve performance when buckets grow too large.

✔ The get() method efficiently retrieves values by using hashCode() and equals().

✔ Ensure hashCode() and equals() are properly overridden for custom objects.

✔ Load factor controls resizing to maintain performance.

Understanding the internal working of HashMap helps in writing efficient Java applications and avoiding common pitfalls like unnecessary duplicates and performance bottlenecks.

Leave a Comment