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