003 Фильтр Блума Bloom filters

Фильтр Блума (Bloom filter) — это вероятностная структура данных, предназначенная для проверки принадлежности элемента множеству. Она позволяет быстро определить, принадлежит ли элемент множеству, но с некоторой вероятностью может ошибаться, указывая, что элемент присутствует, хотя его нет в множестве. Основные Характеристики Память: Использует фиксированное количество памяти и битовую матрицу для хранения данных. Хэш-функции: Для каждой операции проверки или добавления элемента используются несколько хэш-функций, которые вычисляют позиции в битовом массиве. Погрешность: Фильтр может давать ложные положительные ответы, но никогда не дает ложных отрицательных (если фильтр говорит, что элемента нет, его действительно нет). Операции Добавление элемента: Примените несколько хэш-функций к элементу. Установите биты в позициях, указанных хэш-функциями, в значение 1. Проверка наличия элемента: Примените те же хэш-функции к элементу.