Иногда нужно отвечать на вопрос «есть ли элемент?» на огромном множестве, а set слишком прожорлив. Фильтр Блума (Bloom filter) — экономная вероятностная структура. Она даёт только два ответа: «точно нет» или «возможно, да». То есть возможны ложноположительные срабатывания (false positive), а ложноотрицательных не бывает никогда.

Битовый массив: `w6` даёт ложноположительный ответ, а `cow` — «точно нет»
Битовый массив: w6 даёт ложноположительный ответ, а cow — «точно нет»

Идея

  • Массив из m бит, сначала все 0.
  • k разных хеш-функций.
  • add(x): ставит в 1 те k бит, на которые указывают k хешей.
  • x in filter: смотрит те же k бит; если все 1, ответ «возможно, да», если хотя бы один 0, то «точно нет».

Биты переходят только 0 → 1, поэтому добавленный элемент находится всегда (ложноотрицательных нет). Но другие элементы могли поставить те же биты в 1, поэтому и никогда не добавлявшийся элемент может получить «возможно, да».

Реализация

Вместо k отдельных хеш-функций используем два хеша: h1 + i * h2 (приём Кирша и Митценмахера). Хеши берём из hashlib.sha256, чтобы они были детерминированными (hash() меняется между процессами, см. хеш-функции).

python
import hashlib
import math