Collisions

When different keys get the same hash

A collision occurs when different keys produce the same hash or ultimately land in the same bucket. This is not a hash-function error or a rare exception: the number of possible keys is enormous, while the number of hashes and buckets is finite, so collisions cannot be eliminated completely.

record Key(int value) {
    @Override
    public int hashCode() {
        return 1;
    }
}

Map<Key, String> map = new HashMap<>();
map.put(new Key(10), "ten");
map.put(new Key(20), "twenty");

Both keys have the same hashCode(), but they are not equal to each other. A correct hash table must keep both records and distinguish them by the actual keys during lookup.

Two main handling strategies

One approach is separate chaining: each bucket can contain several records. After moving to the required bucket, the table compares the key with the keys stored there. With a good distribution, only a small number of comparisons are needed.

Another approach is open addressing: all records are stored directly in the internal array, and when a position is occupied, the algorithm follows a defined rule to search for another free position. These approaches differ in implementation details, but they serve the same goal — not losing records that compete for the same place.

Why table occupancy matters

The more densely a table is filled, the more often records compete for the same positions and the more work lookup can require. Implementations therefore track a load factor — the ratio of the number of records to the capacity. When the table becomes too full, it can enlarge the internal array and redistribute its elements.

With a good distribution and controlled load, operations remain expectedly close to O(1). If many keys continually land in the same place, the amount of work grows and in the worst case can approach O(n).