Collisions

Definition

A collision happens when two different keys land in the same bucket. The HashMap keeps them together in a chain and uses equals to tell them apart, so the map still works, but a lookup has to compare against more entries.

Example code

Keys with the same hash share one bucket and cost extra equals calls

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

class BadKey {
    static int equalsCalls = 0;
    final String name;
    BadKey(String name) { this.name = name; }

    @Override public int hashCode() { return 1; }                 // every key goes to the same bucket
    @Override public boolean equals(Object o) {
        equalsCalls++;
        return o instanceof BadKey k && k.name.equals(name);
    }
}

class Demo {
    public static void main(String[] args) {
        Map<BadKey, Integer> map = new HashMap<>();
        BadKey last = null;
        for (int i = 1; i <= 5; i++) {
            last = new BadKey("key" + i);
            map.put(last, i);
        }

        BadKey.equalsCalls = 0;
        System.out.println(map.get(new BadKey("key5")));               // still correct...
        System.out.println("equals calls: " + BadKey.equalsCalls);     // ...but it walked the whole chain
    }
}

// Output:
// 5
// equals calls: 5