"""A Bloom filter: k hash positions into one shared bit array.

`add(key)` sets k bits. `key in filt` requires all k of them to be set. So a
query has exactly two possible answers -- "definitely not present" (some bit
was clear) and "maybe present" (all k were set) -- and this toy exists to show
that the "maybe" is not what it looks like. It is not a per-query coin flip.
It is a permanent property of the key: the k positions a key hashes to are
fixed, so a key whose k positions happen to be covered by other members is a
false positive on *every* lookup, forever, for that filter.

Determinism: hashing is SHA-256 from `hashlib`, never Python's builtin
`hash()`. `hash()` is salted per process by PYTHONHASHSEED, so a filter built
on it would poison a different set of keys on every run and none of the
numbers on this page would reproduce. The salt here is an explicit constructor
argument instead of a global, which makes "rehash the filter" a visible
one-line change in the demo rather than an environment variable.
"""

import hashlib
import math


class BloomFilter:
    """m bits, k hash positions per key, one explicit salt."""

    def __init__(self, m, k, salt="A"):
        self.m = m
        self.k = k
        self.salt = salt.encode()
        # One BYTE per bit. A production filter packs 8 bits into each byte
        # (or 64 into a machine word) and pays a shift and a mask per probe.
        # This is 8x more memory and 8x less code, and nothing about the
        # mechanism changes -- see the commentary, section 8.
        self.bits = bytearray(m)
        self.n = 0

    def _indices(self, key):
        """The k positions for `key`, by Kirsch-Mitzenmacher double hashing.

        One SHA-256 of salt+key is split into two 128-bit halves `a` and `b`;
        position i is `(a + i*b) % m`. That is ONE hash computation for all k
        positions rather than k independent hashes, which is what real
        implementations do -- hashing is the only expensive part of a Bloom
        filter, so paying for it once instead of k times is most of the
        performance story.

        `b | 1` forces b odd. If b were ever a multiple of m, every position
        would collapse onto `a` and the filter would silently degrade to k=1.
        For even m, an odd b can never be a multiple of m.
        """
        digest = hashlib.sha256(self.salt + key.encode()).digest()
        a = int.from_bytes(digest[:16], "big")
        b = int.from_bytes(digest[16:], "big") | 1
        for i in range(self.k):
            yield (a + i * b) % self.m

    def add(self, key):
        """Set all k bits for `key`. Idempotent; bits are never cleared."""
        for index in self._indices(key):
            self.bits[index] = 1
        self.n += 1

    def __contains__(self, key):
        """True iff every one of the k bits is set: "maybe", never "yes"."""
        # all() short-circuits, so a true negative usually costs far fewer
        # than k probes: the first clear bit ends the query.
        return all(self.bits[index] for index in self._indices(key))

    def fill_ratio(self):
        """Fraction of the bit array that is set. The filter's whole health."""
        return sum(self.bits) / self.m


def optimal_k(m, n):
    """The k that minimises false positives for m bits and n members.

    Derivation, at whiteboard level. After inserting n keys with k hashes
    each, the chance a given bit is still clear is (1 - 1/m)^(kn), which for
    large m is e^(-kn/m). A false positive needs all k bits set, so the rate
    is (1 - e^(-kn/m))^k. Differentiate and the minimum lands where exactly
    half the bits are set, at k = (m/n) * ln 2.

    Raising k pulls in two directions at once: more bits must all be set for
    a false positive (good), but each insert sets more bits, so the array
    fills faster (bad). Past this k the second effect wins -- see section 6.
    """
    return max(1, round((m / n) * math.log(2)))


def predicted_fp(m, k, n):
    """Textbook false-positive rate: (1 - e^(-kn/m))^k.

    Kept here, executable, so the commentary's arithmetic can be *run* rather
    than asserted. It assumes the k positions are independent and uniform,
    which double hashing only approximates -- section 7 measures the gap.
    """
    return (1 - math.exp(-k * n / m)) ** k


def bits_per_key_for(target_fp):
    """Bits per key needed to hit `target_fp` at the optimal k.

    Substituting k = (m/n) ln 2 into the formula above collapses it to
    fp = 2^(-(m/n) ln 2), so m/n = -log2(fp) / ln 2. The striking consequence:
    the requirement is per KEY, not a fraction of the data. 1% costs ~9.6
    bits per key whether the values are 10 bytes or 10 megabytes.
    """
    return -math.log2(target_fp) / math.log(2)