Can you explain internal working of HashMap in Java?

HashMap is one of the most commonly used data structures in Java for storing key-value pairs. Internally, it uses an array of buckets and a hashing mechanism to provide fast insertion, retrieval, and deletion operations. It achieves near O(1) average time complexity for most operations by efficiently distributing keys across buckets.

Key Points: • HashMap stores data as key-value pairs. • Internally, it uses an array of buckets. • hashCode() determines the bucket location for a key. • equals() is used to identify the correct key within a bucket. • Collision handling is done using Linked Lists and Red-Black Trees (Java 8+).

Internal Structure of HashMap

A HashMap consists of an array called the bucket array.

Simplified View:

Bucket[0] Bucket[1] Bucket[2] Bucket[3] ... Bucket[n]

Each bucket can contain:

• No element • A single node • A Linked List of nodes • A Red-Black Tree of nodes (Java 8+)

Each node stores:

• Key • Value • Hash • Reference to next node

How put() Works

Suppose:

map.put("Java", 100);

Step 1: Calculate Hash Code

hashCode() is called on the key.

Example:

"Java".hashCode()

Step 2: Determine Bucket Index

HashMap converts the hash value into a bucket index.

Formula:

index = hash & (capacity - 1)

Step 3: Store the Entry

If the bucket is empty:

• Create a new node.

If the bucket already contains data:

• Check for matching keys using equals(). • Update the value if the key already exists. • Otherwise add a new node.

How get() Works

Suppose:

map.get("Java");

Step 1:

Calculate hashCode() of the key.

Step 2:

Find the bucket index.

Step 3:

Search the bucket.

• If only one node exists, return its value. • If multiple nodes exist, use equals() to locate the exact key.

Step 4:

Return the associated value.

Collision Handling

A collision occurs when multiple keys map to the same bucket.

Example:

Key A → Bucket 5 Key B → Bucket 5

Both keys cannot occupy the same position directly.

Before Java 8:

Collisions were handled using a Linked List.

Bucket 5:

KeyA -> KeyB -> KeyC

Java 8 and Later:

When the number of nodes in a bucket exceeds a threshold (8 by default), the Linked List is converted into a Red-Black Tree.

Bucket 5:

          KeyB
         /    \

KeyA KeyC

Benefits:

• Faster searching • Improved performance during heavy collisions

Example: Adding employee records into a HashMap.

Code Example:

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

public class Demo {

    public static void main(String[] args) {

        Map<Integer, String> employees =
                new HashMap<>();

        employees.put(101, "John");
        employees.put(102, "David");
        employees.put(103, "Mike");

        System.out.println(
                employees.get(102));
    }
}

Output:

David

Role of hashCode() and equals()

hashCode():

• Identifies the bucket location.

equals():

• Confirms whether two keys are logically equal.

Both methods work together to ensure correct storage and retrieval.

Time Complexity

Operation Average Case

put() O(1)

get() O(1)

remove() O(1)

Worst Case:

O(n)

or

O(log n)

when treeified buckets are involved.

Important HashMap Features

• Allows one null key. • Allows multiple null values. • Not synchronized. • Does not guarantee insertion order. • Uses hashing for fast access.

HashMap vs LinkedHashMap vs TreeMap

HashMap: • No ordering • Fastest average lookup

LinkedHashMap: • Maintains insertion order

TreeMap: • Maintains sorted order • Uses Red-Black Tree internally

Interview Tip: A concise interview answer is:

"HashMap internally uses an array of buckets to store key-value pairs. When a key is inserted, its hashCode() determines the bucket location, and equals() is used to identify the correct key within that bucket. Collisions are handled using Linked Lists and, from Java 8 onwards, Red-Black Trees for better performance. This design enables average O(1) time complexity for insertion and retrieval operations."