Java HashMap Structure and Hash Collision

0. Introduction

HashMap is one of the most commonly used data structures in Java. It provides fast key value lookups and is widely used in both application code and system level libraries. Because of its importance, understanding how HashMap works internally is a frequent Java interview topic.

In this article we focus on two core concepts:

1. The internal structure of HashMap

2. What happens when a hash collision occurs

Understanding these two topics already explains most of how HashMap behaves.

---

1. Internal Structure of HashMap

At a high level, a HashMap is implemented using an array of buckets. Each bucket can store one or more key value entries.

1.1. Basic Structure

Conceptually, a HashMap looks like this:

index      bucket
--------------------------
0          [ ]
1          [ ]
2          [Entry]
3          [Entry -> Entry] // if collision occurs
4          [ ]

Each bucket corresponds to an index in the internal array.

Each stored element is represented by a structure similar to:

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

Important parts:

• hash : cached hash value of the key

• key : the key

• value : the associated value

• next : pointer to the next node in the same bucket

The next pointer is what allows multiple entries to exist in the same bucket.

---

1.2. How a Key is Stored

When we insert a key value pair:

map.put("apple", 10);

The following steps occur.

Step 1. Compute the hash

Java computes the hash of the key using hashCode().

int hash = key.hashCode();

Step 2. Determine the bucket index

The index in the array is calculated using the hash value.

index = hash % arrayLength

In modern implementations, Java uses bit operations instead of % for efficiency.

Step 3. Store the entry

If the bucket is empty, the entry is placed there.

bucket[index] -> Entry

If the bucket already contains entries, a collision occurs.

---

2. Hash Collision

A hash collision occurs when two different keys produce the same bucket index.

Example:

"apple"  -> index 3
"grape"  -> index 3

Even though the keys are different, they map to the same bucket.

This is unavoidable because the number of possible keys is much larger than the number of buckets.

---

2.1. Collision Handling (Linked List)

When a collision happens, HashMap stores the new entry in the same bucket using a linked structure.

index 3

Entry(key1) -> Entry(key2) -> Entry(key3)

Each node points to the next node using the next reference.

Insertion process:

1. Go to the correct bucket

2. Traverse existing nodes

3. Check if the key already exists

4. If not, append the new node

Key comparison uses equals().

---

2.2. Lookup With Collision

When retrieving a value:

map.get("apple");

The following happens.

1. Compute the hash

2. Find the bucket index

3. Traverse the linked nodes in that bucket

4. Compare keys using equals()

Example bucket:

Entry("apple") -> Entry("grape") -> Entry("melon")

The map checks each key until a match is found.

---

3. Time Complexity Impact

Without collisions, operations are very fast.

Average case: O(1)

With many collisions, the map may need to traverse multiple nodes.

Worst case: O(n)

This is why a good hash function is important.

---

✨ Conclusion

HashMap works by storing entries inside an array of buckets. The hash of the key determines which bucket the entry belongs to. When two keys map to the same bucket, a hash collision occurs. Java handles this by storing multiple entries in the same bucket using a linked structure and resolving the correct key with equals().

Understanding this structure explains how HashMap achieves fast lookups and why proper hashCode() and equals()implementations are important.