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

Коротко

Фильтр Блума отвечает на вопрос «есть ли элемент?» так: «точно нет» или «возможно, есть».

Зачем это нужно

Представьте сервис, который проверяет, не был ли URL уже обработан. Множество из 100 миллионов URL займёт гигабайты оперативной памяти.

Фильтр Блума решает ту же задачу примерно за 100 мегабайт при вероятности ошибки 1%. Экономия в десятки раз — ценой того, что иногда он скажет «возможно, есть» про элемент, которого нет.

Ключевое свойство: если фильтр говорит «нет», это гарантированно правда. Ошибка возможна только в одну сторону.

Как устроен

Есть битовый массив длины m, изначально все нули. И k независимых хеш-функций.

Добавление элемента: считаем k хешей, каждый указывает на позицию в массиве, ставим там единицы.

добавляем "кот":  h1=2, h2=5, h3=9
массив: 0 0 1 0 0 1 0 0 0 1 0 0
            ↑     ↑     ↑

Проверка элемента: считаем те же k хешей. Если хотя бы в одной позиции ноль — элемента точно нет. Если везде единицы — возможно, есть.

Почему возможны ложные срабатывания: единицы могли быть поставлены другими элементами. Совпадение всех k позиций не доказывает, что элемент добавляли.

Почему невозможны ложные отрицания: если элемент добавляли, его биты установлены и никогда не сбрасываются.

Реализация на Python

import hashlib
import math


class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        # оптимальные параметры по формулам ниже
        self.size = self._optimal_size(expected_items, false_positive_rate)
        self.hash_count = self._optimal_hash_count(self.size, expected_items)
        self.bits = bytearray((self.size + 7) // 8)
        self.count = 0

    @staticmethod
    def _optimal_size(n: int, p: float) -> int:
        return max(1, int(-n * math.log(p) / (math.log(2) ** 2)))

    @staticmethod
    def _optimal_hash_count(m: int, n: int) -> int:
        return max(1, int(m / n * math.log(2)))

    def _positions(self, item: str):
        # двойное хеширование: из двух хешей получаем k позиций
        data = item.encode()
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], 'big')
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], 'big')

        for i in range(self.hash_count):
            yield (h1 + i * h2) % self.size

    def add(self, item: str) -> None:
        for pos in self._positions(item):
            self.bits[pos // 8] |= 1 << (pos % 8)
        self.count += 1

    def __contains__(self, item: str) -> bool:
        return all(
            self.bits[pos // 8] & (1 << (pos % 8))
            for pos in self._positions(item)
        )


bf = BloomFilter(expected_items=1000, false_positive_rate=0.01)
for word in ['кот', 'пёс', 'ёж']:
    bf.add(word)

print('кот' in bf)     # True
print('пёс' in bf)     # True
print('слон' in bf)    # False (почти наверняка)

Приём с двойным хешированием важен: вместо k независимых хеш-функций считаются две, а остальные получаются как h1 + i·h2. Доказано, что это даёт практически ту же вероятность ошибки при вдвое меньшей работе.

Расчёт параметров

Формулы, которые стоит знать:

Размер массива при n элементах и желаемой вероятности ошибки p:

m = −n · ln(p) / (ln 2)²

Оптимальное число хеш-функций:

k = (m / n) · ln 2

Фактическая вероятность ошибки при заполнении:

p ≈ (1 − e^(−k·n/m))^k

Практические ориентиры:

То есть при 1% ошибок нужно около 10 бит на элемент — против сотен бит у обычного множества строк. Каждый порядок точности стоит примерно 5 дополнительных бит.

Почему нельзя удалять

Сброс бита в ноль сломал бы другие элементы, которые используют ту же позицию. После удаления «кота» проверка «пса» могла бы начать возвращать False — а это уже ложноотрицательный ответ, ради отсутствия которого всё и затевалось.

Решение — счётный фильтр Блума: вместо битов хранятся небольшие счётчики (обычно 4 бита). Добавление увеличивает, удаление уменьшает.

class CountingBloomFilter:
    def __init__(self, size: int, hash_count: int):
        self.counters = [0] * size
        self.size = size
        self.hash_count = hash_count

    def remove(self, item: str) -> None:
        for pos in self._positions(item):
            if self.counters[pos] > 0:
                self.counters[pos] -= 1

Цена — память вырастает в 4 раза.

Где применяется на практике

Базы данных. Cassandra, HBase, RocksDB проверяют фильтром Блума, есть ли ключ в SSTable-файле, прежде чем читать диск. Если фильтр говорит «нет» — чтения не будет, а это самая дорогая операция.

Веб-браузеры. Chrome проверял URL по списку вредоносных сайтов локальным фильтром Блума, обращаясь к серверу только при срабатывании.

Кэши и CDN. «Одноразовые» объекты не кладут в кэш: фильтр помнит, запрашивался ли URL раньше.

Проверка паролей. Список утёкших паролей в фильтре Блума занимает мегабайты вместо гигабайтов.

Дедупликация в системах обработки потоков: отсеять уже виденные события.

Общий паттерн — фильтр как дешёвая предпроверка перед дорогой операцией. Ложное срабатывание стоит одного лишнего обращения, зато отрицательный ответ экономит их массово.

Родственные структуры

Cuckoo filter — поддерживает удаление и при малых вероятностях ошибки компактнее фильтра Блума.

HyperLogLog — отвечает не на «есть ли элемент», а на «сколько различных элементов» с погрешностью около 2% при считанных килобайтах памяти.

Count-Min Sketch — приближённо считает частоты элементов.

Все они относятся к вероятностным структурам: жертвуют точностью ради памяти.

Частые ошибки

Расчёт на точный ответ. Фильтр Блума нельзя использовать там, где ложное срабатывание недопустимо. Он всегда предпроверка, а не источник истины.

Переполнение. При добавлении большего числа элементов, чем заложено, вероятность ошибки растёт нелинейно и быстро приближается к 100%. Следите за заполнением.

Слишком много хеш-функций. Кажется, что больше — надёжнее, но это не так: лишние функции заполняют массив единицами и увеличивают ошибку. Оптимум даёт формула.

Коррелированные хеш-функции. Если функции зависимы, реальная вероятность ошибки будет заметно выше расчётной.

Попытка удаления. Сброс битов ломает структуру. Нужен счётный вариант.

Что запомнить

• Фильтр Блума отвечает «точно нет» или «возможно, да» — ложноотрицательных не бывает.
• Битовый массив плюс k хеш-функций; биты только устанавливаются.
• Около 10 бит на элемент при вероятности ошибки 1%.
• Удаление невозможно без счётного варианта.
• Главный сценарий — дешёвая предпроверка перед дорогим обращением к диску или сети.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→