Probabilistic Data Structures

One-sided membership

A negative rules out a key; a positive needs exact verification. Apple sets {2,5,7}; banana {1,5,9}; absent grape {1,5,7} falsely matches.

Prove the invariant

Insertion only sets required positions. Consistent hashes and no clearing preserve every inserted key. Clearing apple’s shared bit 5 can make banana a false negative. No deletion is offered.

Logical bits are not packed storage

The scaffold uses []bool / a Python list. They are not m packed bits. Packed position p uses byte p/8 and mask 1<<(p%8). m=17 needs 3 payload bytes plus overhead.

Error estimates need assumptions

Approximate FP=(1-exp(-kn/m))^k under ideal hashing assumptions. 10 bits/key and k=7 estimates 0.82%; actual helpers need measurement. Double hashing with h2=0 repeats one position regardless of k.

Design the measurement

Known-absent queries estimate false positives; inserted keys separately check false negatives. Record m, k, key population and sample size. Hashing an L-unit key separately k times costs O(k(L+1)), not simply O(k).