FA-73273 / Probabilistic sketches / Member archive

Cuckoo filter with partial-key relocation: alternate bucket hashed from the full item · case 03

Relocated fingerprints move to buckets that lookups never check, producing false negatives.

Member previewVariant 3 · 3 implementations · 10 checks per implementation

Case contract

Input {m (power of two), max_kicks, ops} with pre-hashed 32-bit items. Fingerprint f is bits 24-31, with 0 remapped to 1 (0 marks an empty slot in packed tables). i1 = h mod m and the alternate bucket is alt(i, f) = (i XOR (f*0x5bd1e995 mod 2^32)) mod m, so it is computable from the fingerprint alone. Buckets hold 2 fingerprints. Insert tries i1, then i2, then performs up to max_kicks evictions starting at i1, swapping slot (kick mod 2); on failure the table is restored and "full" is returned. Delete removes one copy, from i1 first. Return [results, buckets].

Why this case matters

Cuckoo filters give deletable approximate membership for caches and dedup stores; relocation only works if the alternate bucket is derivable from the stored fingerprint.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
fill 0 m=4 kicks=3	`[["ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "full", true, false, true, true, false, true, false, false, false], [[48, 140], [115, 99], [105, 13], [35, 120]]]`	`[["ok", "ok", "ok", "ok", "ok", "ok", "ok", "ok", "full", true, true, true, true, true, true, true, false, false], [[140, 35], [115], [48, 105], [120, 13]]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.