Java.Collections.Why Do Keys with Different Hash Codes End Up in the Same Bucket in a HashMap?

Yes, I know! In HashMap (and other hash-based data structures), keys with different hash codes can end up in the same bucket due to the mechanics of hashing and bucket indexing.

---

Why Does This Happen?

1. The Bucket Array Has a Limited Size (capacity)
   • HashMap uses an array to store entries, with a default capacity of 16.
   • The bucket index is calculated using a bitwise AND (&) operation.
2. Index Calculation in HashMap

int bucketIndex = (hashCode) & (capacity - 1);

Even if two objects have different hash codes, after applying this formula, they can produce the same index. Example:

• hashCode(A) = 18, hashCode(B) = 34
• If capacity = 16, their bucket indices will be:

18 & (16 - 1) = 18 & 15 = 2
34 & (16 - 1) = 34 & 15 = 2

1. • Both will be placed in bucket #2.
2. Collisions Are Inevitable
   • Even if we had an infinite array, at some point, different objects would still map to the same index.
   • To handle collisions, HashMap uses linked lists or balanced trees (since Java 8, if there are more than 8 elements in a bucket).

---

What Happens When a Collision Occurs?

• If different keys end up in the same bucket, HashMap handles them by:
  1. Using a Linked List (before Java 8).
  2. Using a Red-Black Tree (Java 8+, if there are more than 8 elements in a bucket).
  3. Distinguishing Keys Using equals(), since hash codes alone are not enough.

---

Code Example

import java.util.HashMap;

class Key {
    private final int id;

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

    @Override
    public int hashCode() {
        return id; // Simulating different hash codes
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Key && this.id == ((Key) obj).id;
    }
}

public class HashMapCollisionExample {
    public static void main(String[] args) {
        HashMap<Key, String> map = new HashMap<>(16); // capacity = 16
        Key key1 = new Key(18); // 18 & 15 = 2
        Key key2 = new Key(34); // 34 & 15 = 2

        map.put(key1, "Value1");
        map.put(key2, "Value2"); // Both end up in the same bucket

        System.out.println(map.get(key1)); // "Value1"
        System.out.println(map.get(key2)); // "Value2" - different keys distinguished by equals
    }
}

Output:

Value1
Value2

Summary: Why Do Different Hash Codes Map to the Same Bucket?

1. Bucket index = hashCode & (capacity - 1) → The number of available buckets is limited.
2. Different numbers can produce the same index (bitwise masking effect).
3. Collisions are resolved using linked lists (before Java 8) or red-black trees (Java 8+).

That’s why interviewers love to ask:
“What happens if two keys fall into the same bucket?”
It’s important to understand how HashMap works under the hood! 🔥