Фильтр Блума: как быстро проверить отсутствие элемента

Что такое фильтр Блума и зачем он нужен?

Представьте, что нужно проверить, есть ли элемент в огромном наборе данных, но хранить все элементы слишком дорого. Фильтр Блума — структура данных, которая на вопрос «этот элемент точно отсутствует?» отвечает без ошибок, а на «возможно, присутствует» может ошибиться. Это звучит как магия, но на самом деле — гениальный компромисс между памятью и точностью.

Фильтр Блума используется в базах данных (Cassandra, HBase, LevelDB), кешах CDN, браузерах для проверки вредоносных URL и распределённых системах. Везде, где быстрее сказать «нет», чем тратить время на поиск.

Как работает фильтр Блума

Фильтр Блума — это битовый массив из m бит, изначально все нули, и k хеш-функций.

• Добавление ключа (add(key)): вычислить k хешей ключа, установить соответствующие биты в 1.
• Проверка (check(key)): вычислить те же k хешей. Если хотя бы один бит равен 0 — ключ точно не добавляли. Если все биты равны 1 — ключ возможно, присутствует.

Ложных отрицаний нет: если ключ добавили, его биты установлены, и проверка всегда скажет «возможно, присутствует». Но биты общие: разные ключи могут установить одни и те же биты, и тогда для недобавленного ключа все биты окажутся единицами — ложное срабатывание.

Пример на Python

import hashlib
import math

class BloomFilter:
    def __init__(self, m: int, k: int):
        self.m = m                     # размер битового массива
        self.k = k                     # количество хешей
        self.bits = [0] * m            # битовый массив

    def _hashes(self, item: str):
        # используем двойное хеширование: h1 + i*h2 mod m
        h1 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.sha1(item.encode()).hexdigest(), 16)
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item: str):
        for pos in self._hashes(item):
            self.bits[pos] = 1

    def check(self, item: str) -> bool:
        for pos in self._hashes(item):
            if self.bits[pos] == 0:
                return False          # точно не добавляли
        return True                    # возможно, добавляли

# Пример использования
bf = BloomFilter(100, 3)
bf.add("apple")
bf.add("banana")
print(bf.check("apple"))   # True (возможно)
print(bf.check("orange"))  # False (точно нет)

Как найти ложное срабатывание

В демо-версии можно добавить несколько слов и нажать кнопку «Найти ложное срабатывание». Алгоритм перебирает слова, которых вы не добавляли, и проверяет, не совпали ли их биты с уже установленными. Когда такое слово находится, фильтр говорит «возможно, присутствует», хотя вы его не добавляли. Это наглядно показывает компромисс: вы храните не сами ключи, а их «тени» на битовом массиве, и тени перекрываются.

Почему ложные срабатывания приемлемы?

Потому что ответ «точно нет» часто важнее и не содержит ошибок. В базах данных проверка фильтра Блума перед чтением с диска: если «точно нет» — пропускаем чтение. Ложное срабатывание — всего один лишний запрос, а ложное отрицание привело бы к потере данных. Поэтому гарантия отсутствия ложных отрицаний критична.

Настройка фильтра Блума

Вероятность ложного срабатывания после добавления n элементов:

p ≈ (1 − e^(−kn/m))^k

Два параметра:

• m (количество бит) — чем больше, тем меньше коллизий и ниже ошибка. Это ваш бюджет памяти.
• k (количество хешей) — оптимальное значение: k = (m/n)·ln 2. Слишком мало — коллизии вероятны, слишком много — массив заполняется быстрее, и вероятность растёт.

На практике не нужно k независимых хеш-функций. Используют двойное хеширование: h_i = h1 + i·h2 mod m на основе двух базовых хешей. Это даёт k хороших индексов.

Практический вывод

Фильтр Блума — мощный инструмент для экономии памяти, когда можно допустить редкие ложные срабатывания. Попробуйте реализовать его самостоятельно для задачи проверки уникальности URL или кеша. Настройте параметры под свои данные и убедитесь в эффективности.