Фильтр Блума
Вот как работает Фильтр Блума:
- Инициализация: Сначала создается битовый массив (битовая карта) фиксированного размера, и все его биты устанавливаются в 0.
- Хеш-функции: Определяется набор хеш-функций, которые могут отображать элементы в биты битового массива. Каждая хеш-функция принимает элемент и выдаёт индекс бита в массиве.
- Добавление элементов: Когда элемент добавляется в Фильтр Блума, для него вычисляются значения всех хеш-функций, и соответствующие биты в битовом массиве устанавливаются в 1.
- Проверка наличия элемента: Для проверки наличия элемента вычисляются значения всех хеш-функций для этого элемента. Если все соответствующие биты в битовом массиве установлены в 1, то Фильтр Блума сообщает, что элемент "возможно присутствует". Если хотя бы один из битов равен 0, то элемент точно отсутствует.
- Ложные срабатывания: Фильтр Блума может давать ложные срабатывания, то есть сообщать, что элемент присутствует, когда он на самом деле отсутствует. Это связано с тем, что разные элементы могут хешироваться в одинаковые биты.
Применение Фильтра Блума:
- Кэширование: Есть ли данные в кэше, чтобы избежать ненужных операций чтения из базы данных или других хранилищ.
- Сетевые приложения: Фильтрации пакетов данных или запросов.
- Поисковые системы. Содержится ли слово в индексе, без хранения всего индекса в памяти.
- Безопасность. Проверки наличия вредоносных файлов в больших наборах файлов.
- Антивирусные программы