Фильтр Блума
Предположим, что вы пишете программу для работы с файловой системой. Вам нужно определить, какие файлы находятся у вас на диске. Можно обратиться к файловой системе, пробежаться по директориям, но это долго. Первое, что приходит в голову, — использовать словарь. Да, если использовать словарь, основанный на хэш-таблице, то это будет константная сложность. Вроде круто. Но хэш-таблица хранит объект. А он нам нужен? На помощь нам приходит фильтр Блума. В отличие от хэш-таблицы, это вероятностная структура. Как и хэш-таблица, он имеет константную сложность. Он может гарантировать, что элемент отсутствует, но не может гарантировать, что он есть. Он не хранит объект, за счёт чего занимает меньше памяти.
Фильтр Блума используется много где, например в базах данных (PostgreSQL, Cassandra), в браузерах, даже Биткоин использовал его в своё время.
