Hash table collision resolution works because a table never assumes that one hash route belongs to only one key. When two or more keys map to the same bucket or initial slot, the table follows a deterministic rule that keeps all entries reachable and lets later lookups distinguish them by equality.
The two classic families are separate chaining and open addressing. Chaining stores multiple colliding entries behind one bucket. Open addressing stores entries inside the main table and follows a probe sequence until it finds the key or an available position.
This pillar explains collision inevitability, separate chaining, linear probing, quadratic probing, double hashing, clustering, load factor, deletion, tombstones, probe termination, equality checks, locality, adversarial collisions and the correctness invariants that keep keys discoverable after collisions.
Read the master guide: How Hash Tables Work · How Hash Table Lookup Works · How X Works Hub
The Direct Answer: Collision Resolution Keeps Different Keys Reachable
A collision occurs when two different keys are routed to the same bucket or initial table position.
Collision resolution defines what happens next. The table must preserve both entries, later find either one from its key, and support updates and deletion without breaking search.
Correctness depends on the resolution rule being used consistently for insert, lookup and delete.
Collisions Are Unavoidable
A table has finitely many positions while the key universe is usually far larger.
By the pigeonhole principle, different keys must sometimes share the same reduced location.
The engineering question is therefore not whether collisions happen but how cheaply and safely they are handled.
A Good Hash Function Reduces Collisions but Cannot Ban Them
Good distribution spreads expected keys across the address space.
That keeps chains and probe sequences short on average.
But exact collision freedom is impossible for an unrestricted dynamic key universe.
Separate Chaining Gives Each Bucket a Collection
In chaining, the table array stores a bucket object or reference, and that bucket stores all entries whose hashes route there.
Lookup searches only that bucket and compares keys for equality.
Insertion appends or inserts a new entry unless an equal key already exists.
A Chain Need Not Literally Be a Linked List
Textbooks often draw linked lists, but a bucket can be a dynamic array, small vector, tree or hybrid structure.
The abstract invariant is simply that all entries assigned to the bucket remain searchable there.
Implementation details determine locality, deletion cost and worst-case behaviour.
Chaining Can Tolerate Load Factor Above One
If there are more entries than buckets, chaining can still function because multiple entries can live in each bucket.
Expected lookup cost grows with average bucket population.
Resizing keeps those populations from becoming too large.
Open Addressing Stores Entries in the Main Array
Open addressing uses empty table slots as the storage for entries themselves.
If the initial slot is occupied by another key, the algorithm tries another slot according to a probe sequence.
All entries remain inside the primary table storage.
A Probe Sequence Is the Collision Route
For a key with hash h, the implementation defines a sequence of candidate slots.
Insertion uses that sequence to find a valid place. Lookup must follow the compatible sequence to recover the key later.
The probe rule is therefore part of the key’s address.
Linear Probing Checks Nearby Slots
Linear probing commonly checks consecutive positions after the initial index, wrapping around the table as needed.
It is simple and cache-friendly because adjacent memory locations are visited.
Its weakness is primary clustering: occupied runs can grow and attract more insertions.
Primary Clustering Creates Long Runs
When a run of occupied slots forms, any key hashing anywhere into that run may be placed at its end.
The run gets longer, which increases the chance that future keys collide with it.
This positive feedback can degrade probe lengths.
Quadratic Probing Spreads Successive Probes Differently
Quadratic probing uses a growing offset pattern rather than checking each next slot linearly.
This can reduce primary clustering.
Coverage properties depend on table size and the exact probe formula, so implementations must choose compatible parameters.
Double Hashing Uses a Second Hash for the Step
Double hashing derives a probe step from another hash-like function.
Different keys that share an initial slot can then follow different probe paths.
The step must be chosen so the probe can reach the necessary table positions under the capacity scheme.
Open Addressing Requires Spare Capacity
If every slot is occupied, a new distinct key has nowhere to go.
Performance becomes poor well before absolute fullness because probes lengthen as empty slots become rare.
This is why open-addressed tables usually maintain a load threshold below one.
Lookup and Insertion Must Use Compatible Probing
A key inserted after probing five slots can only be found later if lookup follows the same search sequence from the same initial hash conditions.
Any mismatch between insertion and lookup rules loses keys.
The probe sequence is a correctness invariant.
Equality Still Resolves Identity
A probe reaches entries that happen to occupy candidate slots.
Hash or probe position narrows candidates, but equality decides whether the requested key has been found.
Collision handling never removes the need for exact comparison.
Deletion Is Easy in Chaining
Find the entry in its bucket and remove it from that bucket’s local structure.
Other entries remain reachable because the bucket itself still contains the rest of the chain.
Exact cost depends on bucket representation.
Deletion Is Subtle in Open Addressing
Suppose key B collided with key A and was inserted later in the probe sequence.
If A is deleted and its slot is changed to ‘never occupied’, lookup for B may stop at that newly empty slot and incorrectly report absence.
The table needs a deletion representation that preserves the probe path.
Tombstones Preserve Search Continuity
A tombstone marks a slot as deleted but previously occupied.
Lookup continues past it because a desired key could be farther along the probe sequence.
Insertion may often reuse a tombstone under appropriate rules.
Tombstones Accumulate Search Debt
Deleted slots no longer store useful entries but can still lengthen probes.
A table with many tombstones can have low live load yet poor lookup performance.
Rehashing or compaction may be needed to remove the dead markers.
Backward-Shift Deletion Is Another Strategy
Some linear-probing variants move later entries backward after deletion while preserving their legal probe reachability.
This can remove the need for persistent tombstones.
The relocation rule must be careful not to move an entry before a slot its lookup would ever probe.
Robin Hood Hashing Changes Placement Priorities
Robin Hood hashing tracks or infers probe distance and may swap entries so keys with long probe distances take better positions.
The goal is to reduce variance in search lengths rather than simply accept first-empty placement.
It is an advanced open-addressing strategy built on the same reachability invariants.
Cuckoo Hashing Gives Keys Multiple Candidate Homes
Cuckoo hashing uses multiple hash functions or candidate positions.
Insertion can evict an existing entry to its alternate position, potentially triggering a chain of relocations.
Lookup can be very fast because only a small set of candidate positions must be checked.
Cuckoo Cycles Can Force Rebuilds
Relocations may enter a cycle where no arrangement fits under the current functions and capacity.
The table can rebuild with new hash choices or larger capacity.
Collision resolution sometimes turns insertion into a global rearrangement.
Hopscotch and Swiss-Style Tables Optimise Locality
Modern high-performance hash tables use control metadata, neighbourhood invariants and vector-friendly scans to make collision search efficient on real hardware.
The exact techniques vary, but they still solve the same basic problem: represent collisions while keeping candidate search short and cache-friendly.
Textbook chaining versus probing is the foundation; production designs refine it.
Clustering Is a Spatial Performance Problem
Two tables can have the same number of collisions but very different performance if one concentrates them into long clusters.
Probe locality, distribution and cluster growth matter.
Average occupancy alone does not describe every performance effect.
Load Factor Interacts With Collision Strategy
Chaining can function at higher load because buckets contain multiple entries.
Open addressing needs enough empty slots to terminate searches quickly.
Resize thresholds therefore depend on the underlying resolution method.
Expected Probe Length Rises With Occupancy
As open-addressed tables fill, the chance of finding an empty slot quickly falls.
Both insertion and unsuccessful lookup can become expensive.
Capacity policy protects collision performance before total saturation.
Hash Quality and Probing Quality Are Jointly Responsible
A perfect probe formula cannot compensate for a hash that maps all common keys to the same small region without cost.
Likewise a good hash can still suffer from a poor collision policy at high load.
Performance is an interaction between routing and resolution.
Adversarial Collisions Can Attack Chaining
If an attacker can force many keys into one bucket, lookup can become proportional to bucket size.
Randomised hashing or tree-based collision buckets can make such attacks harder or reduce their worst-case impact.
Security-sensitive runtimes treat hash-table collision behaviour as an attack surface.
Adversarial Inputs Can Also Attack Open Addressing
Predictable clustering or long probe sequences can consume CPU even if memory remains bounded.
Randomisation and robust mixing reduce predictability.
Expected performance assumptions should reflect whether inputs are trusted.
Bucket Treeification Can Improve Worst Cases
Some library hash maps transform a heavily collided bucket from a list-like structure into a balanced tree after thresholds are crossed.
This preserves fast ordinary cases while limiting pathological chain search.
Such behaviour is an implementation policy, not a universal property of chaining.
Locality Favors Open Addressing
Probe sequences can inspect contiguous control bytes or entries stored close in memory.
Modern processors often reward this with fewer cache misses than pointer-heavy chaining.
This practical advantage helps explain the popularity of sophisticated open-addressed tables.
Stable References Can Favor Chaining in Some Designs
If entries are separately allocated, resizing bucket arrays may not require moving the entry objects themselves.
Some applications value pointer or iterator stability.
Concrete guarantees vary by container.
Collision Resolution Affects Iteration Layout
Chaining iterates bucket collections; open addressing scans table slots.
Neither naturally implies sorted order.
Any insertion-order guarantee usually comes from extra structure.
Collision Resolution Affects Memory Overhead
Chaining can incur pointers or per-bucket allocation overhead.
Open addressing reserves empty slots and control metadata.
Memory efficiency depends on load target, entry size and implementation.
Small Keys and Values Can Make Metadata Dominant
If each logical entry is only a few bytes, pointers, hashes, tombstones and unused capacity can dominate memory usage.
Compact open-addressing designs can be attractive in these cases.
Data-structure overhead should be evaluated relative to payload size.
Large Entries Can Change the Trade-Off
If values are large objects stored by reference anyway, bucket metadata may be a smaller fraction of total memory.
Chaining’s pointer overhead may matter less.
Workload and payload shape influence the best strategy.
A Collision Does Not Necessarily Mean Slow Lookup
One or two extra comparisons or probes are often cheap.
Performance fails when collision structure becomes systematically long or unpredictable.
The objective is controlled collision cost, not literal zero collisions.
Collision Statistics Are Useful Diagnostics
Measure bucket-size distributions, average and maximum probe lengths, tombstone counts and load factor.
These metrics reveal whether poor performance comes from hash quality, occupancy or deletion history.
Operational visibility makes data-structure tuning evidence-based.
Insertion Can Trigger More Work Than Lookup
Open addressing may search for an empty slot after confirming the key is absent. Some advanced strategies relocate entries.
Chaining may allocate or grow a bucket container.
Collision strategy affects update cost differently from read cost.
Update of an Existing Key Should Not Duplicate It
If lookup finds an equal key during insertion, the map updates the value according to API semantics.
Collision handling must distinguish ‘same key encountered’ from ‘different key sharing location’.
Equality controls that branch.
A Common Failure: Stopping at the First Occupied Slot
Open-addressing lookup sees a different key in the initial slot and reports absence.
That ignores the probe sequence used at insertion.
A collision means search must continue.
A Common Failure: Clearing a Deleted Slot
The slot is marked never-used instead of tombstoned or repaired.
Keys later in the probe sequence become unreachable.
Deletion must preserve search continuity.
A Common Failure: Probe Sequence Cannot Cover Needed Slots
Quadratic or double-hash parameters interact badly with capacity, causing the sequence to cycle through only part of the table.
Insertion may fail despite free slots elsewhere.
Probe mathematics and capacity policy must be compatible.
A Common Failure: Load Factor Too High
Open addressing is allowed to approach full occupancy.
Probes become long and variance spikes.
Resize before crowding destroys the expected performance regime.
A Common Failure: Tombstones Never Cleaned
A delete-heavy workload leaves a trail of markers.
Live occupancy looks low while probe paths remain long.
Track effective occupancy including deleted slots when deciding when to rebuild.
A Common Failure: Bucket Structure Becomes Pathological
Chaining uses a linear bucket structure under adversarial collisions and never defends the worst case.
Application latency becomes proportional to one giant bucket.
Choose hash randomisation, treeification or other safeguards where threat models require them.
Navigation Perspective: Collision Resolution Is What Happens When the Map Pin Is Not Unique
The hash gets several keys to the same neighbourhood. Chaining gives the neighbourhood a directory. Open addressing says: if this address is occupied, follow this route to the next candidate.
The route must be reproducible later or the key cannot be found.
Collision resolution is local navigation under ambiguous coordinates.
Cross-Disciplinary Perspective: Collision Strategy Is a Systems Choice
An algorithms student compares expected complexity. A runtime engineer compares cache locality. A security engineer watches collision attacks. A memory engineer counts metadata. A real-time engineer cares about latency spikes.
All are evaluating the same question from different constraints: what should happen when the first address is already taken?
The answer shapes the table’s entire performance profile.
A Practical Collision-Resolution Checklist
Is the table chained or open-addressed? What is the probe or bucket structure? What load factor is considered safe? How is deletion represented? Can probe sequences cover the required slots? How are long collision chains defended? What metrics reveal clustering? Are untrusted keys possible? What reference or iterator guarantees matter?
Collision handling should be understood before relying on headline O(1) claims.
It is the mechanism that makes hashing correct under inevitable ambiguity.
Frequently Asked Question: Which Is Better, Chaining or Open Addressing?
Neither is universally better. Chaining can simplify deletion and tolerate higher load; open addressing can offer excellent locality and compactness.
Choose based on workload, memory, latency, implementation and API guarantees.
Frequently Asked Question: Why Not Use a Better Hash and Avoid Collisions?
No finite hash mapping can uniquely encode an unrestricted larger key space.
Better hashing reduces systematic clustering; it does not remove the need for a collision rule.
Frequently Asked Question: Why Do Tombstones Exist?
They distinguish ‘this slot was used, so keep probing’ from ‘this slot has never been used, so the key cannot be farther along this probe sequence.’
That distinction preserves lookup correctness after deletion.
Frequently Asked Question: What Is Clustering?
Clustering is the formation of groups of occupied slots or correlated probe paths that cause future operations to examine more locations.
Linear probing is particularly associated with primary clustering.
The Pillar Boundary: What This Article Owns
This article owns hash-table collision resolution: separate chaining, open addressing, probing, clustering, deletion reachability, tombstones and collision-related performance.
The lookup pillar owns the end-to-end key retrieval path. The resizing pillar owns capacity and rehash policy. The master ties them together.
General-purpose hashing remains owned by the earlier hashing article.
Sources and Further Reading
For chaining and hash functions, see the MIT 6.006 hashing lecture notes index, including Hashing I.
For open addressing, see MIT OpenCourseWare: Open Addressing and Cryptographic Hashing.
For a modern overview of hashing as a data-structure technique, see MIT OpenCourseWare: Lecture 4 — Hashing.
Final Synthesis: Collision Resolution Is the Table’s Promise Not to Lose Ambiguous Keys
Hashing deliberately compresses a huge key space into a smaller address space, so collisions are inevitable.
Collision resolution turns that ambiguity into a deterministic local search. Chaining groups colliding entries behind a bucket. Open addressing gives them alternative slots along reproducible probe paths.
The table remains correct only because insertion, lookup and deletion all preserve the same reachability rules.
Continue the Hash Table Series
How Hash Tables Work · How Hash Table Lookup Works · How X Works Hub
