FA-73290 / Probabilistic sketches / Member archive

Cuckoo filter with partial-key relocation: delete removes every copy · case 05

Deleting one of several identical inserts removes all of them.

Member previewVariant 5 · 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
triple insert then delete	`[["ok", "ok", "ok", true, false], [[], [], [], []]]`	`[["ok", "ok", "ok", true, true], [[], [], [61], [61]]]`	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.