DSA DSA In Depth
0%
From-Scratch Build

Space-Efficient Bloom Filter & Fingerprint Cuckoo Filter

A Kirsch-Mitzenmacher double-hashed Bloom filter and a partial-key Cuckoo filter supporting dynamic deletions, fingerprint buckets, and false-positive rate telemetry.

~35 min Advanced Lessons: Bloom Filters, Counting Bloom Filters, Cuckoo Filters & Xor Filters, Variance Reduction: Robin Hood Hashing (PSL) & Cuckoo Hashing, Hash Functions: Division, Multiplicative, Universal & k-Independent Families, Count-Min Sketch & Streaming Frequency Estimation Error Bounds, HyperLogLog: Harmonic Mean & Stochastic Averaging in 1.5 KB, Production Case Study: Google Abseil SwissTable & Rust hashbrown SIMD Probing
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Overview

A Kirsch-Mitzenmacher double-hashed Bloom filter and a partial-key Cuckoo filter supporting dynamic deletions, fingerprint buckets, and false-positive rate telemetry.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Kirsch-Mitzenmacher Double Hashing

  • Core Mechanical Concept: Simulating k Hash Functions with Two Base Hashes
  • Target Module: index.js (BloomFilter._bitPosition)
  • Engineering Specification: Implement _bitPosition(item, i) on BloomFilter. Using h1 = hashA(String(item)) and h2 = hashB(String(item)), return ((h1 + Math.imul(i, h2)) >>> 0) % this.bitCount.
  • Verification Invariant: derives k independent bit positions from two base hashes

Step 2: Packed Uint32Array Bitset Operations

  • Core Mechanical Concept: Word-Level Bit Addressing via (bit >>> 5) and (1 << (bit & 31))
  • Target Module: index.js (BloomFilter.add / BloomFilter.mightContain)
  • Engineering Specification: Implement add(item) and mightContain(item) on BloomFilter. Bit b resides in 32-bit word b >>> 5 at bit offset b & 31. A Bloom filter guarantees 0% false negatives.
  • Verification Invariant: guarantees zero false negatives and bounded false positives

Step 3: Partial-Key Cuckoo Hashing via XOR Symmetry

  • Core Mechanical Concept: Computing Alternate Bucket from Fingerprint Alone: i2 = i1 ^ hash(fp)
  • Target Module: index.js (CuckooFilter._indices)
  • Engineering Specification: Implement _indices(item) on CuckooFilter. Because XOR is an involution ($x \oplus y \oplus y = x$), defining i2 = (i1 ^ hashA(String(fp))) & mask allows us to compute a displaced fingerprint’s alternate bucket from (currentIdx, fp) without storing the original key!
  • Verification Invariant: computes involutory alternate bucket indices via XOR

Step 4: Cuckoo Kick-Out Displacement & Safe Deletion

  • Core Mechanical Concept: Bounded Eviction Chains & Fingerprint Removal
  • Target Module: index.js (CuckooFilter.insert / CuckooFilter.delete)
  • Engineering Specification: Implement insert(item) and delete(item) on CuckooFilter. 1. In insert: place fp in buckets[i1] or buckets[i2] if space exists; otherwise loop up to maxKicks times swapping curFp with a slot in buckets[idx] and jumping to idx = _altIndex(idx, curFp). 2. In delete: remove one matching fp from buckets[i1] or buckets[i2].
  • Verification Invariant: inserts with Cuckoo displacement and deletes without false negatives

Asymptotic & Memory Layout Guarantees

  • Category: Hashing & Sketches
  • Difficulty: Advanced (~35 minutes)
  • Key Architectural Highlights:
    • Kirsch-Mitzenmacher double-hashing Bloom filter with Uint32Array bitset
    • Partial-key Cuckoo filter computing alternate bucket via i2 = i1 ^ hash(fp)
    • Dynamic deletion support with zero false negatives and bounded kick-out displacement
  • Tags & Primitives: Bloom Filter, Cuckoo Filter, Kirsch-Mitzenmacher, XOR Partial-Key Cuckoo, Probabilistic Sketch

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.