ohbf/README.md

ohbf: One-Hashing Bloom Filter

A small Python implementation of the One-Hashing Bloom Filter (OHBF) from

Jianyuan Lu, Tong Yang, Yi Wang, Huichen Dai, Linxiao Jin, Haoyu Song, Bin Liu. "One-Hashing Bloom Filter." IEEE IWQoS 2015. https://yangtonghome.github.io/uploads/One_Hashing.pdf

Standard library only (hashlib, math). Python 3.11+.

The idea

A standard Bloom filter with k hash functions computes k hashes per key and reduces each one modulo the same array size m. The paper splits that work into two stages: the expensive hash stage (key → machine word) and the cheap modulo stage (word → index). OHBF keeps the modulo stage, drops all but one hash, and reduces that one hash against k different moduli instead.

To do that, the m-bit array is split into k partitions with sizes m_1 … m_k, each close to m/k and pairwise coprime. A key is hashed once to a large integer h, and its bit in partition i is h mod m_i. Insert sets those k bits. Lookup checks them and stops at the first zero.

The coprimality is what makes this work. By the Chinese Remainder Theorem, if h is uniform over a range that is a multiple of m_i · m_j, then h mod m_i and h mod m_j are independent (the paper's Lemma 2 and Theorem 1). If two sizes share a factor, one position leaks information about the other. With sizes 5 and 10, h mod 10 fixes h mod 5, so only 10 of the 50 possible position pairs can occur. The tests check this directly.

The partition sizes come from the paper's Algorithm 1: choose k consecutive primes whose sum is closest to the target m. Distinct primes are always coprime, and consecutive primes near m/k are close in size. That keeps the false-positive rate almost identical to a standard Bloom filter's (Eq. 6):

fp ≈ ∏ᵢ (1 − (1 − 1/mᵢ)ⁿ)

Usage

from ohbf import OneHashBloomFilter, choose_partitions

f = OneHashBloomFilter.from_capacity(100_000, 0.01)   # n, target fp rate
f.add("alice")
f.add(b"\x00raw bytes")
"alice" in f          # True
"bob" in f            # almost certainly False
f.sizes               # (136883, 136889, ..., 136963), k = 7 consecutive primes
f.bit_count           # 958475 total bits (target was 958506)
f.positions("alice")  # the k per-partition indices, for debugging
f.expected_fp_rate()  # Eq. 6 at the current len(f)

# Explicit sizes are validated:
OneHashBloomFilter((5, 7, 11))      # ok
OneHashBloomFilter((6, 9, 11))      # ValueError: not pairwise coprime

# Inject a hash (receives the key as UTF-8 bytes, returns an int):
OneHashBloomFilter((5, 7, 11), hash_fn=lambda b: {b"apple": 100}[b])

choose_partitions(10_000, 10)  # [971, 977, ..., 1031], sum 10012 (paper Table II)

Keys may be str (encoded as UTF-8) or bytes. Bits live in one bytearray. Partition i starts at a fixed bit offset in that array.

Running

python3.12 -m venv .venv && .venv/bin/pip install pytest
.venv/bin/python -m pytest
.venv/bin/python examples/demo.py

The demo:

1. Steps through a hand example with sizes (5, 7, 11) and fixed hashes. After inserting apple (h=100) and pear (h=37), it prints each partition's bits. grape (h=345 → positions 0, 2, 4) is reported present even though it was never added. That is a false positive.
2. Builds from_capacity(100_000, 0.01) and compares the observed false-positive rate with Eq. 6.
3. Times add and lookup on 1 KB keys against a baseline filter that makes k separate salted blake2b calls. On one M-series Mac run, add was about 4x faster and lookup about 3x faster. Your numbers will differ. Hashing 1 KB dominates per-key cost here, so the saving shows clearly. With short keys, Python interpreter overhead hides much of it.

Hashing

The default hash is blake2b. Its digest size is the smallest number of bytes giving at least log2(m_1 · … · m_k) + 64 bits, capped at blake2b's 512 bits. The 64 spare bits bound the modulo bias at ∏mᵢ / 2^bits ≤ 2⁻⁶⁴. This stands in for the paper's suggestion to discard the top 2^L mod ∏mᵢ values.

Caveats

• Pairwise, not full, independence. Theorem 1 proves that any two partition positions are independent. It does not prove that all k are jointly independent. In practice the Eq. 6 estimate matches observed rates closely (see the tests and demo), but the guarantee is pairwise only.
• Hash width grows with k. The guarantee requires the hash range to be much larger than ∏mᵢ, roughly k · log2(m/k) bits. For k = 7 partitions of about 137K bits, that is 184 bits. For large k (e.g. k = 32, m = 10⁶) it exceeds 512 bits. The filter then uses the full 512-bit digest and emits a UserWarning. The paper reports that OHBF still works well in that case.
• Total size is approximate. Sums of consecutive primes are discrete, so bit_count differs slightly from the requested m. The paper reports at most 315 bits of difference for k = 32 and m < 10⁷.
• Modulo cost. Each lookup does k big-integer modulo operations on a wide h, against different and non-power-of-two divisors. The saving is in hashing, not in modulo arithmetic. When keys are short and the hash is cheap, the gain shrinks. A C implementation could reduce h to 64 bits per partition first or use fast-modulo tricks; this one does not.
• Algorithm 1 as printed. In the paper's pseudocode, the final loop copies the window that just failed the diff ≥ min test, not the best one. choose_partitions returns the best window, which is the stated goal. It reproduces every row of the paper's Table II, and a test checks that.
• No deletion, serialization, or union. It is a teaching-sized implementation.

License

MIT