Advanced & Probabilistic Hashing
Cuckoo Hashing with guaranteed O(1) worst-case lookups, Robin Hood probing PSL variance minimization, and Bloom Filters false-positive math.
Reinforce your mental model: run, pause, and inspect live pointers with our interactive visualizer:
Topics Covered:
45. Cuckoo Hashing (Two Independent Hash Functions & Guaranteed Worst-Case Lookup) • 46. Robin Hood Hashing (Probe Sequence Length Variance Minimization) • 47. 2-Level Perfect Hashing (FKS Scheme with Zero Collisions & Space Proof) • 48. Probabilistic Streaming Hashing (Bloom Filters, Dimensioning Proofs & Count-Min Sketch)
Standard hashing algorithms achieve average-case latency, but suffer from potential degradation under adversarial inputs or high load factors. Advanced hashing architectures conquer these performance limits through two distinct paradigms: deterministic worst-case guarantees and sublinear probabilistic approximation. This chapter analyzes Cuckoo Hashing's multi-choice displacement eviction, Robin Hood probe sequence length variance reduction, Fredman-Komlós-Szemerédi (FKS) two-level perfect hashing with space proofs, Bloom filter dimensioning equations, and Count-Min sketch streaming frequency estimation.
Learning Objectives
#- Formulate Cuckoo Hashing's displacement eviction algorithm and prove its guaranteed worst-case lookup in at most two memory reads.
- Implement Robin Hood Hashing and evaluate how probe sequence length (PSL) variance reduction enables early search termination.
- Formalize the FKS (Fredman-Komlós-Szemerédi) two-level perfect hashing scheme and prove why expected total space is strictly despite quadratic secondary buckets.
- Derive optimal Bloom Filter sizing formulas (, ) and implement production probabilistic filters with zero false negatives.
- Implement the Count-Min Sketch frequency estimator and explain why the operation across independent hash rows filters out collision noise.
Topic 45: Cuckoo Hashing
#1. Conceptual Architecture & The Cuckoo Invariant
In standard open addressing or separate chaining, worst-case lookup latency degrades to under high load factors or adversarial collision attacks. Cuckoo Hashing (Pagh & Rodler, 2001) guarantees that every lookup executes in strictly worst-case time, requiring at most two memory accesses:
The Lookup Superpower:
To locate key , the algorithm inspects and . If neither slot contains , the key is guaranteed not to exist in the table. Lookup never probes a third slot!
The Displacement Eviction Protocol (Kicking Chain):
Insertion mimics the breeding parasitism of the European cuckoo chick, which pushes host eggs out of the nest:
- Attempt to insert key into table at slot .
- If is empty, place and terminate.
- If is occupied by existing key , evict and store .
- Displaced key must now be inserted into its alternative nest in at .
- If is occupied by , evict and re-insert into at .
- Repeat this displacement chain until an empty slot is encountered or a loop cycle is detected (chain length exceeds threshold ).
- If a cycle occurs, the table is over-constrained; allocate larger tables and rehash all elements with fresh hash functions.
#include <vector>
#include <optional>
#include <cstdint>
template <typename K, typename V>
class CuckooHashTable {
private:
struct Entry {
K key;
V value;
bool occupied = false;
};
size_t capacity_;
std::vector<Entry> table1_;
std::vector<Entry> table2_;
static constexpr size_t MAX_LOOP = 64;
size_t hash1(const K& key) const {
return (std::hash<K>{}(key) * 0x9e3779b97f4a7c15ULL) % capacity_;
}
size_t hash2(const K& key) const {
return (std::hash<K>{}(key) * 0xc6a4a7935bd1e995ULL) % capacity_;
}
public:
explicit CuckooHashTable(size_t cap = 1024)
: capacity_(cap), table1_(cap), table2_(cap) {}
std::optional<V> find(const K& key) const {
size_t p1 = hash1(key);
if (table1_[p1].occupied && table1_[p1].key == key) {
return table1_[p1].value;
}
size_t p2 = hash2(key);
if (table2_[p2].occupied && table2_[p2].key == key) {
return table2_[p2].value;
}
return std::nullopt; // Strictly at most 2 memory reads!
}
bool insert(K key, V value) {
if (find(key).has_value()) return false; // Key already present
K curr_key = std::move(key);
V curr_val = std::move(value);
for (size_t step = 0; step < MAX_LOOP; ++step) {
// Attempt in Table 1
size_t p1 = hash1(curr_key);
if (!table1_[p1].occupied) {
table1_[p1] = {std::move(curr_key), std::move(curr_val), true};
return true;
}
std::swap(curr_key, table1_[p1].key);
std::swap(curr_val, table1_[p1].value);
// Attempt in Table 2
size_t p2 = hash2(curr_key);
if (!table2_[p2].occupied) {
table2_[p2] = {std::move(curr_key), std::move(curr_val), true};
return true;
}
std::swap(curr_key, table2_[p2].key);
std::swap(curr_val, table2_[p2].value);
}
// Cycle detected: table requires resizing and rehash
rehash(capacity_ * 2);
return insert(std::move(curr_key), std::move(curr_val));
}
private:
void rehash(size_t new_cap) {
auto old1 = std::move(table1_);
auto old2 = std::move(table2_);
capacity_ = new_cap;
table1_.assign(capacity_, Entry{});
table2_.assign(capacity_, Entry{});
for (auto& e : old1) if (e.occupied) insert(e.key, e.value);
for (auto& e : old2) if (e.occupied) insert(e.key, e.value);
}
};Topic 46: Robin Hood Hashing
#1. Probe Sequence Length (PSL) & Variance Reduction
#Standard linear probing suffers from severe variance in probe lengths: while some keys land in their initial hash bucket (), other keys are swept into long primary clusters with or even .
Robin Hood Hashing (Pedro Celis, 1985) equalizes search latency across all keys by enforcing an egalitarian rule:
"Steal from the rich, give to the poor."
- Rich Element: An element residing close to its initial hashed bucket (small PSL / Distance from Initial Bucket, DIB).
- Poor Element: An element that has probed far from its initial hashed bucket (large PSL / DIB).
2. The Robin Hood Invariant & Swapping Mechanism
#During insertion of candidate with current probe count :
- Probe index .
- If slot is empty, insert with and stop.
- If slot contains an existing element with distance :
- If : The incoming element is poorer than the resident! Swap them! The incoming element claims the slot, and the evicted resident continues probing with probe distance .
- If : Increment and continue probing next slot.
3. Early Search Termination
#In traditional open addressing, an unsuccessful search must probe continuously until it hits an EMPTY slot.
In Robin Hood Hashing, search for key at probe step can terminate early:
Proof: Because the Robin Hood invariant strictly maintains sorted DIBs within any collision cluster, if key existed, it would have evicted any element with a smaller DIB. Seeing an element with proves could never have probed past this position.
#include <vector>
#include <optional>
#include <cstdint>
#include <utility>
template <typename K, typename V>
class RobinHoodHashTable {
private:
struct Entry {
K key;
V value;
int dib = -1; // -1 indicates EMPTY
};
size_t capacity_;
size_t size_;
std::vector<Entry> table_;
public:
explicit RobinHoodHashTable(size_t cap = 16)
: capacity_(cap), size_(0), table_(cap) {}
std::optional<V> find(const K& key) const {
size_t initial = std::hash<K>{}(key) % capacity_;
int dist = 0;
while (dist < static_cast<int>(capacity_)) {
size_t idx = (initial + dist) % capacity_;
if (table_[idx].dib == -1 || dist > table_[idx].dib) {
// Early termination guarantee!
return std::nullopt;
}
if (table_[idx].key == key) {
return table_[idx].value;
}
++dist;
}
return std::nullopt;
}
void insert(K key, V value) {
if (size_ * 10 >= capacity_ * 9) rehash(capacity_ * 2); // 90% load factor threshold
size_t initial = std::hash<K>{}(key) % capacity_;
Entry incoming{std::move(key), std::move(value), 0};
while (incoming.dib < static_cast<int>(capacity_)) {
size_t idx = (initial + incoming.dib) % capacity_;
if (table_[idx].dib == -1) {
table_[idx] = std::move(incoming);
++size_;
return;
}
if (table_[idx].key == incoming.key) {
table_[idx].value = std::move(incoming.value);
return; // Updated existing key
}
// Robin Hood Stealing Invariant:
if (incoming.dib > table_[idx].dib) {
std::swap(incoming, table_[idx]);
initial = (std::hash<K>{}(incoming.key) % capacity_);
}
++incoming.dib;
}
}
private:
void rehash(size_t new_cap) {
auto old = std::move(table_);
capacity_ = new_cap;
size_ = 0;
table_.assign(capacity_, Entry{});
for (auto& e : old) {
if (e.dib != -1) insert(std::move(e.key), std::move(e.value));
}
}
};Topic 47: 2-Level Perfect Hashing (The FKS Scheme)
#1. Zero Collisions in Static Sets: The FKS Architecture
#Devised by Michael Fredman, János Komlós, and Endre Szemerédi (1984), FKS Perfect Hashing solves the static dictionary problem with:
- Strictly worst-case lookup time (exactly 2 memory accesses).
- Strictly total space.
2. The Quadratic Secondary Bucket Invariant
#Let be the number of keys hashed to primary bucket . Primary table size is chosen as . For each bucket , construct a secondary table of size:
Why ? The Birthday Paradox Bound:
In a secondary table with keys and capacity , by choosing a 2-universal hash family , the expected number of collisions is:
By Markov's Inequality:
3. Formal Proof of Total Space
#The total space consumed by all secondary tables is . Using 2-universal hashing at Level 1 ():
Thus, the expected total space for all secondary tables combined is strictly less than , proving that FKS Perfect Hashing guarantees worst-case lookup in total space.
Topic 48: Probabilistic Streaming Hashing & Modern Industrial Tables
#1. Conceptual Architecture & Zero False Negatives
A Bloom Filter (Burton H. Bloom, 1970) is a space-efficient probabilistic data structure designed to test whether an element is a member of a set:
- No False Negatives: If the filter returns
false, the element is guaranteed not to be in the set. - Potential False Positives: If the filter returns
true, the element might be in the set with bounded probability .
2. Formal Mathematical Sizing Derivation
#Let be the bit-array length, be the number of inserted elements, and be the number of independent hash functions:
- Probability a specific bit remains after one hash: .
- Probability bit remains after elements inserted:
- Probability of a False Positive (all bits for a new key are 1):
- Differentiating with respect to yields the Optimal Number of Hash Functions:
- Minimum required bits for desired false positive rate :
Practical Rule: For a false positive rate (), allocate approximately and .
3. Production Implementations
#C++20 Standard-Compliant Bloom Filter
#include <vector>
#include <string_view>
#include <cmath>
#include <cstdint>
class BloomFilter {
private:
std::vector<bool> bits_;
size_t num_bits_;
size_t num_hashes_;
// Kirsch-Mitzenmacher optimization: generate k hashes using 2 hash functions:
// gi(x) = (h1(x) + i * h2(x)) mod m
uint64_t hash1(std::string_view s) const {
uint64_t h = 14695981039346656037ULL; // FNV-1a 64-bit
for (char c : s) {
h ^= static_cast<unsigned char>(c);
h *= 1099511628211ULL;
}
return h;
}
uint64_t hash2(std::string_view s) const {
uint64_t h = 0;
for (char c : s) {
h = (h * 131) + static_cast<unsigned char>(c);
}
return h;
}
public:
BloomFilter(size_t expected_elements, double false_positive_rate) {
num_bits_ = static_cast<size_t>(-1.0 * expected_elements * std::log(false_positive_rate) / (std::log(2) * std::log(2)));
num_hashes_ = static_cast<size_t>((static_cast<double>(num_bits_) / expected_elements) * std::log(2));
if (num_hashes_ < 1) num_hashes_ = 1;
bits_.assign(num_bits_, false);
}
void insert(std::string_view key) {
uint64_t h1 = hash1(key);
uint64_t h2 = hash2(key);
for (size_t i = 0; i < num_hashes_; ++i) {
size_t bit_idx = (h1 + i * h2) % num_bits_;
bits_[bit_idx] = true;
}
}
[[nodiscard]] bool contains(std::string_view key) const {
uint64_t h1 = hash1(key);
uint64_t h2 = hash2(key);
for (size_t i = 0; i < num_hashes_; ++i) {
size_t bit_idx = (h1 + i * h2) % num_bits_;
if (!bits_[bit_idx]) {
return false; // Definitively absent!
}
}
return true; // Probabilistically present
}
};C++20 Count-Min Sketch for Streaming Frequency Estimation
#include <vector>
#include <string_view>
#include <cmath>
#include <algorithm>
#include <cstdint>
class CountMinSketch {
private:
size_t width_;
size_t depth_;
std::vector<std::vector<uint32_t>> table_;
uint64_t hash(std::string_view key, size_t row) const {
// Universal hash generation using Murmur-style mixing seeds
uint64_t h = 0xcbf29ce484222325ULL ^ (row * 0x9e3779b97f4a7c15ULL);
for (char c : key) {
h ^= static_cast<unsigned char>(c);
h *= 0x100000001b3ULL;
}
return h % width_;
}
public:
// eps: error factor (width = ceil(e / eps))
// delta: error probability (depth = ceil(ln(1 / delta)))
CountMinSketch(double eps, double delta) {
width_ = static_cast<size_t>(std::ceil(std::exp(1.0) / eps));
depth_ = static_cast<size_t>(std::ceil(std::log(1.0 / delta)));
table_.assign(depth_, std::vector<uint32_t>(width_, 0));
}
void update(std::string_view key, uint32_t count = 1) {
for (size_t r = 0; r < depth_; ++r) {
size_t c = hash(key, r);
table_[r][c] += count;
}
}
[[nodiscard]] uint32_t estimate(std::string_view key) const {
uint32_t min_count = UINT32_MAX;
for (size_t r = 0; r < depth_; ++r) {
size_t c = hash(key, r);
min_count = std::min(min_count, table_[r][c]);
}
return min_count; // Taking minimum across rows filters out collision noise
}
};4. Modern Industrial Hash Table Architecture: Swiss Tables & SIMD Control Bytes
#Traditional hash tables (including std::unordered_map and classical linear probing) suffer severe CPU cache misses due to pointer chasing and iterating over full sizeof(Key + Value) memory slots during probing.
Developed by Matt Kulukundis at Google for the Abseil library (absl::flat_hash_map) and adopted as the default hash table in the Rust standard library (hashbrown):
- Split Metadata & Payloads: Control metadata is decoupled from entries. Probing only scans 1-byte control words, fitting up to 64 slots into a single L1 cacheline.
- SIMD 16-Way Parallel Matching: A 64-bit hash is partitioned into (lower 57 bits for group indexing) and (top 7 bits as a fingerprint). Using 128-bit vector instructions (e.g. SSE2
_mm_cmpeq_epi8), 16 control bytes are tested in parallel in a single CPU instruction! - Bitmask Candidate Extraction: The vector comparison returns a 16-bit mask of matching candidates. The CPU hardware instruction
std::countr_zeroimmediately yields the matching slot index, achieving unprecedented throughput.
Module 04 Summary & Key Takeaways
#- Cuckoo Hashing Guarantee: Guaranteed worst-case lookup in at most 2 memory reads via displacement eviction.
- Robin Hood Early Termination: Tracking PSL and swapping "poorer" elements minimizes variance and guarantees early exit on missing keys.
- FKS Perfect Hashing: Uses two-level hashing with quadratic secondary buckets to guarantee zero collisions in strictly expected space.
- Bloom Filter Precision: Zero false negatives with sublinear bits ( bits/key for error) using Kirsch-Mitzenmacher dual-hash expansion.
- Count-Min Frequency Estimation: Sublinear memory frequency estimation bounding collision overestimates via independent minimums.
- Swiss Tables Efficiency: SIMD 16-way vector probing over decoupled 1-byte control words eliminates cacheline pollution.
Authoritative Academic & Practice Compendium
#Primary Academic Literature
#- Pagh, R., & Rodler, F. F. (2004). Cuckoo Hashing. Journal of Algorithms, 51(2), 122–144.
- Celis, P. (1985). Robin Hood Hashing. PhD thesis, Technical Report CS-85-37, University of Waterloo.
- Fredman, M. L., Komlós, J., & Szemerédi, E. (1984). Storing a sparse table with worst case access time. Journal of the ACM, 31(3), 538–544.
- Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422–426.
- Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 58–75.
- Kulukundis, M. (2017). Designing a Fast, Efficient, Cache-friendly Hash Map, Step by Step. CppCon Presentation, Google Abseil.
Authoritative Visualizers & External Curricula
#- VisuAlgo Hash Table: Interactive visualizer demonstrating separate chaining, linear probing, quadratic probing, and collision resolution traces.
- GeeksforGeeks Hashing Data Structure: Complete tutorials on universal hashing, open addressing, and collision handling.
High-Yield LeetCode Practice Suite
#- LeetCode 706: Design HashMap (Easy/Medium) — Foundational bucket array, chaining, and open addressing implementations.
- LeetCode 705: Design HashSet (Easy/Medium) — Bitset and collision array design.
- LeetCode 128: Longest Consecutive Sequence (Medium) — hash set lookups with streak boundary testing.
- LeetCode 49: Group Anagrams (Medium) — Canonical hash key canonicalization and frequency tuple hashing.