Bloom Filter

Структура — это битовый массив длины m (изначально все нули) и k независимых хеш-функций h₁, ..., h_k, каждая отображающая элемент в позицию [0, m). Добавление элемента x устанавливает в единицу все k битов h₁(x), ..., h_k(x). Проверка "содержится ли x" вычисляет те же k позиций и отвечает "да" только если все k битов установлены в единицу — если хотя бы один ноль, x точно не добавлялся (иначе этот бит был бы установлен при добавлении). Именно из этого следует отсутствие ложных отрицаний: бит, установленный при вставке, никогда не сбрасывается обратно (классический Bloom Filter не поддерживает удаление), поэтому проверка добавленного элемента гарантированно находит все его биты единицами.The structure is a bit array of length m (initially all zeros) and k independent hash functions h₁, ..., h_k, each mapping an element to a position in [0, m). Adding an element x sets to 1 all k bits h₁(x), ..., h_k(x). Checking "does x exist" computes the same k positions and answers "yes" only if all k bits are set — if even one is zero, x definitely wasn't added (otherwise that bit would have been set on insertion). This is exactly why there are no false negatives: a bit set on insertion is never cleared back (a classic Bloom filter doesn't support deletion), so checking an added element is guaranteed to find all its bits set.

Ложные срабатывания возникают именно потому, что разные элементы делят один и тот же битовый массив: если добавлено достаточно элементов, случайное совпадение может установить все k бит какого-то никогда не добавлявшегося элемента просто как побочный эффект вставок других элементов. Вероятность этого растёт с числом добавленных элементов и падает с размером массива m — управляемый, а не катастрофический компромисс.False positives arise precisely because different elements share the same bit array: with enough elements added, a random coincidence can end up setting all k bits of some never-added element purely as a side effect of other insertions. This probability grows with the number of added elements and shrinks with the array size m — a manageable trade-off, not a catastrophic one.

class BloomFilter {
    std::vector<bool> bits;
    size_t k;
public:
    BloomFilter(size_t m, size_t num_hashes) : bits(m, false), k(num_hashes) {}

    void add(const std::string& item) {
        for (size_t i = 0; i < k; ++i)
            bits[hash_i(item, i) % bits.size()] = true;
    }

    bool might_contain(const std::string& item) const {
        for (size_t i = 0; i < k; ++i)
            if (!bits[hash_i(item, i) % bits.size()]) return false;  // хоть один 0 — точно нет// even one 0 — definitely absent
        return true;                                              // все 1 — возможно да// all 1s — possibly present
    }
};

Битовый массив снизу. При добавлении k позиций подсвечиваются и устанавливаются в единицу. При проверке позиции подсвечиваются жёлтым — зелёный итог означает "возможно да", красный — "точно нет" на первом же встреченном нуле.The bit array is shown below. On add, k positions are highlighted and set to 1. On check, positions are highlighted yellow — a green result means "possibly yes," red means "definitely no" at the first zero found.

Для n добавленных элементов, m бит и k хеш-функций вероятность ложного срабатывания приближённо равна (1 - e^(-kn/m))^k. Эта функция минимизируется по k при фиксированных m и n значением k = (m/n)·ln(2) — то есть оптимальное число хеш-функций зависит только от отношения "бит на элемент". При оптимальном k минимальная достижимая вероятность ошибки примерно 0.6185^(m/n) — формула, показывающая, что вероятность ошибки падает экспоненциально с ростом m/n: удвоение памяти на элемент не удваивает точность, а возводит её в квадрат по вероятности ошибки.For n added elements, m bits, and k hash functions, the false-positive probability is approximately (1 - e^(-kn/m))^k. This function is minimized over k, for fixed m and n, at k = (m/n)·ln(2) — meaning the optimal number of hash functions depends only on the "bits per element" ratio. At the optimal k, the minimum achievable error probability is roughly 0.6185^(m/n) — a formula showing the error probability drops exponentially as m/n grows: doubling memory per element doesn't double accuracy, it squares the error probability.