Detecting and Fixing Bad Distribution

In one line

You can check hash quality empirically: bit density should be uniform across regions of the array, measured FPR on known non-members should match (1 − e^(−kn/m))^k, and the estimated count from the fill ratio should match the real count. Deviations point to weak hashes, bugs in index arithmetic or skewed keys.

0/3 · 0%

Think of it like this

Checking whether a lottery machine is fair by drawing many times and counting how often each number comes up. If some numbers appear far more often, something is wrong with the machine.

Key ideas

01
Density histogram: split the bit array into, say, 1,024 regions and compute each region's fill. With good hashing they're all close to the overall fill (small variance); hot regions reveal clustering.
02
Empirical FPR: query a large sample of guaranteed non-members (for example strings with a prefix never used for members) and compare the rate with the formula.
03
Count estimate: n_est = −(m/k) ln(1 − fill). If it's much lower than the number of distinct items you inserted, positions are overlapping too much.
04
Common bugs: negative modulo results in Java (Math.abs(Integer.MIN_VALUE) is negative), using 32-bit hashes on arrays larger than 2^32, a constant h2 of zero, and serializing with one hash and reading with another.
05
Fix and verify with a test suite that runs these three checks on every change to hashing code.

Code & diagrams

density_check.pypython

import math, statistics

def density_report(bits: bytearray, m: int, k: int, inserted: int, regions: int = 1024):
    per = m // regions
    fills = []
    for r in range(regions):
        ones = sum((bits[i // 8] >> (i % 8)) & 1 for i in range(r * per, (r + 1) * per))
        fills.append(ones / per)
    fill = statistics.mean(fills)
    print(f"fill={fill:.3f} region stdev={statistics.pstdev(fills):.4f}")
    print(f"estimated n={-(m / k) * math.log(1 - fill):,.0f} vs inserted={inserted:,}")
    print(f"predicted FPR={fill ** k:.4%}")
# good hash:  fill=0.518 region stdev=0.0049  estimated n=999,412 vs inserted=1,000,000
# bad hash:   fill=0.431 region stdev=0.2107  estimated n=  789,020 vs inserted=1,000,000

Explain it without notes

How does a lower-than-expected fill ratio indicate bad hashing?

Practice

Add a density and FPR check to your filter's unit tests and make them fail deliberately by swapping in a bad hash.

Trade-offs

↔
Statistical tests need large samples to be reliable; keep them in CI but run them on realistic data sizes.

Done when you can

I can measure hash quality with density, FPR and count-estimate checks.