Collision Handling

A collision happens when two distinct keys land in the same bucket. Collisions are not a sign that hashing is broken. They are unavoidable because the universe of possible keys is usually much larger than the number of buckets in the table.

The important question is how the table behaves after the collision. A strong hash table keeps collisions local, resolves them predictably, and resizes before bucket crowding becomes the normal case. That is what preserves expected O(1) insert, lookup, and delete.

Separate chaining stores a small collection at each bucket. If several keys map to the same bucket, the table searches only that bucket collection and uses equality checks to find the exact key. Conceptually, each bucket can be a linked list of entries.

Java HashMap uses chaining, and since Java 8, very crowded buckets can be converted into balanced trees under specific conditions. This treeification reduces the impact of pathological collision chains, but it is a safety mechanism rather than the expected everyday path. In normal use, good hashing and resizing keep bucket sizes small.

Open addressing stores entries directly inside the bucket array. When a bucket is occupied by a different key, the table probes other positions according to a rule. Linear probing checks nearby buckets in sequence. Quadratic probing jumps by growing offsets. Other variants use a second hash to choose the probe step.

The trade-off is locality versus clustering. Open addressing can be memory efficient and cache friendly because entries live in one array, but high load factors make probe sequences longer. Deletion also needs care, because removing an entry must not break the search path for keys inserted later.

As the table fills, collisions become more frequent. Resizing allocates a larger bucket array and reassigns existing entries to new bucket positions. This is often called rehashing because bucket indices depend on the current capacity, even if each key hash stays the same.

The resize itself costs O(n) for the entries moved, but it happens occasionally. Spread across many operations, that cost is amortized, so individual operations remain expected O(1). This is why interview answers can safely use HashMap and HashSet for linear-time algorithms while still acknowledging occasional resizing.

The expected bound assumes the keys are reasonably distributed. If many keys collide into the same bucket or probe cluster, operations can degrade. With simple chaining, a lookup through one long bucket can be O(n). With open addressing, a nearly full table can require many probes.

In interviews, mention the expected and worst case precisely: hash tables give expected O(1) operations with good hashing and controlled load factor, but adversarial collisions can make operations O(n) unless the implementation has extra protections.