Overview
Cuckoo hashing gives each key two or more possible locations. Inserting a colliding key evicts the current occupant and relocates it to its alternate location until the table stabilizes or needs rebuilding.
CoreSource checked
Cuckoo Hashing
Resolves hash collisions by moving keys between multiple candidate buckets.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Hashing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
dictionary storagehashingclause learninghash lookupdata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use when lookup speed is more important than simple insertion behavior.
- Use when occasional rebuilds are acceptable.
When Not to Use
- Avoid when insertion latency must be tightly bounded.
- Avoid when hash functions cannot be chosen independently enough.
What It Does
- Computes multiple candidate buckets for each key
- Evicts and relocates colliding keys during insertion
- Rehashes when relocation cycles become too long
Use Cases
- Hash tables with fast worst-case lookups
- Membership dictionaries where lookup probes should stay small
- Teaching collision resolution by displacement
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.Compute candidate buckets for the key
- 2.If any candidate bucket is empty, place the key there
- 3.Otherwise evict one occupant and place the new key
- 4.Repeat with the evicted key and its alternate bucket
- 5.If the displacement limit is exceeded, rebuild with new hash functions
Canonical Example
- Input
- insert key K whose first bucket is occupied and alternate bucket is free
- Output
- K placed in the alternate bucket after one displacement or choice
- Explanation
- The key is stored in one of its allowed locations so lookup checks only those locations.
Implementation Notes
- Track displacement count during insertion.
- Use stash or rehash handling for cycles if the design requires it.
- Test adversarial keys and high-load inserts.
Common Pitfalls
- Insertion cycles require a displacement limit and rehash policy.
- High load factors sharply increase rebuild frequency.
- Using correlated hash functions undermines the candidate-bucket model.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow placing each key in one of several hash-determined locations and relocating conflicts on a small dictionary storage example.
Step 1 of 5: Compute candidate buckets for the key
data-structures-mechanismNotes
Cuckoo hashing makes lookup predictable by moving insertion complexity into displacement and rebuild handling.
Sources (1)
What each reference supports for this entry.
Cuckoo Hashing
PaperOriginal reference for two-table cuckoo hashing, displacement chains, and worst-case lookup behavior.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofHash Table
Cuckoo hashing is a hash-table collision strategy.
Alternative toRobin Hood Hashing
Robin Hood hashing equalizes probe distances, while cuckoo hashing relocates keys among candidate buckets.
Conceptual neighborBloom Filter
Both are hashing-based membership structures with different accuracy and storage tradeoffs.
Related Algorithms
Tags
Data StructureHashing