---
title: "Cuckoo Hashing"
description: "Cuckoo hashing restricts each key to two candidate cells, moving collisions into insertion. Read it to separate worst-case lookup from expected amortized updates, replay an eviction chain, and see why empty space alone cannot guarantee a valid placement."
canonical_url: "https://fanout.sh/daily/2026-10-08-cuckoo-hashing"
md_url: "https://fanout.sh/daily/2026-10-08-cuckoo-hashing.md"
last_updated: "2026-10-08"
access: "public"
---

# Cuckoo Hashing

Cuckoo hashing restricts each key to two candidate cells, moving collisions into insertion. Read it to separate worst-case lookup from expected amortized updates, replay an eviction chain, and see why empty space alone cannot guarantee a valid placement.

## Paper details

- Authors: Rasmus Pagh and Flemming Friche Rodler

- Venue: Journal of Algorithms 2004

- Track: Systems

- Difficulty: Easy

- Reading time: 28 min

- Original paper: https://www.rasmuspagh.net/papers/cuckoo-jour.pdf

## What you will learn

- How two legal homes per key bound lookup while allowing insertion to displace residents.

- Why three keys sharing two candidate cells cannot fit, even in a mostly empty table.

- Which randomness and space assumptions support the update guarantee, and where historical benchmarks stop.

## Continue exploring

[Compare consistent hashing](https://fanout.sh/system/archive/consistent-hashing): Contrast assigning keys to servers with assigning keys to cells inside a dictionary; the two hashing problems have different constraints.

---
This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included.

Browse the public content map: https://fanout.sh/sitemap.md