What happens when two keys have the same hash code? How would you handle this scenario?

A situation where two different keys produce the same hash code is known as a hash collision. HashMap handles collisions by storing multiple entries in the same bucket and then using the equals() method to distinguish between keys. This ensures that each key-value pair remains uniquely identifiable even when hash codes are identical.

Key Points: • Two different objects can have the same hash code. • A hash collision does not mean the objects are equal. • HashMap uses equals() to differentiate keys within the same bucket. • Collisions are handled using Linked Lists and Red-Black Trees (Java 8+). • Proper implementation of hashCode() and equals() is essential for correct behavior.

What Is a Hash Collision?

A hash collision occurs when two different keys generate the same hash value.

Example:

Key A → hashCode() = 100

Key B → hashCode() = 100

Even though the hash codes are identical, the objects may represent different data.

How HashMap Handles Collisions

Step 1:

Calculate the hash code of the key.

Step 2:

Determine the bucket index.

Step 3:

If another entry already exists in that bucket:

• Compare keys using equals(). • If equals() returns true, update the existing value. • If equals() returns false, store both entries in the same bucket.

Before Java 8:

Bucket Structure:

KeyA -> KeyB -> KeyC

A Linked List was used to store colliding entries.

Java 8 and Later:

If a bucket contains more than 8 entries, the Linked List is converted into a Red-Black Tree.

Tree Structure:

          KeyB
         /    \

KeyA KeyC

Benefits:

• Faster lookup • Better performance during heavy collisions

Example: Suppose two employee objects generate the same hash code.

Code Example:

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

class Employee {

    private int id;

    Employee(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {

        return 100;
    }

    @Override
    public boolean equals(Object obj) {

        if (this == obj) {
            return true;
        }

        if (!(obj instanceof Employee)) {
            return false;
        }

        Employee emp = (Employee) obj;

        return this.id == emp.id;
    }
}

public class Demo {

    public static void main(String[] args) {

        Map<Employee, String> map =
                new HashMap<>();

        map.put(new Employee(101), "John");
        map.put(new Employee(102), "David");

        System.out.println(map.size());
    }
}

Output:

2

Although both objects return the same hash code, HashMap stores them separately because equals() identifies them as different objects.

Role of equals() During Collisions

hashCode():

• Finds the bucket.

equals():

• Identifies the exact key within that bucket.

Without equals():

HashMap would not be able to distinguish keys correctly.

Performance Impact of Collisions

No Collision:

put() → O(1) get() → O(1)

Many Collisions:

Linked List: • O(n)

Red-Black Tree (Java 8+): • O(log n)

How to Minimize Collisions?

• Implement hashCode() properly. • Use fields that uniquely identify the object. • Ensure good distribution of hash values. • Follow the hashCode() and equals() contract.

Real-World Example:

Consider a banking application storing Account objects as HashMap keys.

Even if two accounts accidentally produce the same hash code:

• HashMap places them in the same bucket. • equals() determines which account is being accessed. • Data remains accurate and retrievable.

Interview Tip: A concise interview answer is:

"When two keys generate the same hash code, a hash collision occurs. HashMap stores both entries in the same bucket and uses the equals() method to distinguish between them. In Java 8 and later, heavily populated buckets are converted from Linked Lists to Red-Black Trees to improve lookup performance from O(n) to O(log n)."