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

```python
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

```sh
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