Что такое фильтр Блума и какой компромисс он делает?

Question

Accepted Answer

**Фильтр Блума** — это пространственно-эффективная **вероятностная** структура, которая отвечает на вопросы о принадлежности к множеству с одним нюансом: она может давать **ложные срабатывания**, но **никогда ложные пропуски**. "Определённо отсутствует" — это уверенность; "возможно присутствует" требует проверки.

## Как это работает

Битовый массив из `m` бит и `k` хеширующих функций. Чтобы **добавить** элемент, установите `k` бит, на которые он хешируется. Чтобы **запросить**, проверьте эти `k` бит — если какой-то равен 0, элемента определённо нет.

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## Code

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| Операция | Время | Память |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Нет ложных пропусков; частота ложных срабатываний падает по мере роста `m` (и настроенного `k`).

## Компромиссы

- **Преимущества:** крошечная потребность в памяти по сравнению с хранением полных ключей; операции за константное время.
- **Недостатки:** ложные срабатывания; **невозможно удалить** (стандартный фильтр Блума); невозможно перечислить элементы.

## Почему это важно

Фильтры Блума дёшево пропускают дорогостоящие операции: базы данных (например Cassandra, HBase) используют их, чтобы избежать чтения с диска для ключей, которых **определённо** нет на диске.

Они воплощают классический компромисс систем — примите небольшой, ограниченный процент ошибок в обмен на значительное снижение потребления памяти и операций ввода-вывода.