Конспект: словарь языка и фильтр Блума

Понятия

Словарь настоящего языка (dict, HashMap, unordered_map) - хеш-таблица со ВСЕМИ приёмами раздела: хеш-функция (для строк со случайной СОЛЬЮ - защита от HashDoS), разрешение коллизий (Python - открытая адресация ради локальности), контроль α, рехеширование.

Неизменяемость ключей - ключом может быть только неизменяемый объект (число, строка, кортеж; НЕ список/словарь). Причина: номер ячейки считается по СОДЕРЖИМОМУ ключа - изменишь ключ после вставки, его хеш «уедет», и он потеряется.

Соль хеша строк - hash() строки подмешивает случайное семя, выбранное при старте процесса. Внутри запуска детерминирован, между запусками разный. Нельзя закладываться на конкретные хеши и порядок set.

__hash__ и __eq__ - свой класс-ключ обязан задавать их согласованно: равные объекты → равный хеш (иначе словарь их не найдёт).

Фильтр Блума - вероятностная структура на m бит и k хеш-функций для проверки наличия при крошечной памяти. Добавить x: выставить биты h₁(x)…hₖ(x) в 1. Проверить: хоть один 0 → «ТОЧНО НЕТ» (надёжно), все 1 → «ВОЗМОЖНО ЕСТЬ» (ложноположительное с вероятностью p).

Односторонняя ошибка - ложноотрицательных НЕТ (биты не сбрасываются), ложноположительные ЕСТЬ (бит не помнит, кто его выставил). Удалять нельзя (испортишь чужие биты).

Размер фильтра - k ≈ 0.69·m/n, память ≈ 1.44·log₂(1/p) бит на элемент (≈ 10 бит на p = 1%) - в разы меньше хранения самих элементов.

Что унести

Две практические структуры на хеше - точная и вероятностная.

Словарь: d[key] - это «хеш с солью → ячейка → пробы → сравнение ключа», и все его «странные» правила (неизменяемые ключи, пляшущие hash(), __hash__+__eq__) - прямые следствия устройства. O(1) в среднем, не в худшем.

Фильтр Блума - дешёвый ПРЕДФИЛЬТР: доверяй «точно нет» (отменяет дорогую проверку - диск, сеть, полную базу), «возможно есть» перепроверяй. Так работают базы (Cassandra, RocksDB) перед чтением диска, браузеры/антивирусы по спискам URL, проверка паролей на утечку.

Ловушки джокера

Изменяемый объект как ключ (список). unhashable, а через костыль - потеряется при изменении.

Закладываться на конкретные hash() / порядок set между запусками. Они солятся - код сломается непредсказуемо. Нужен воспроизводимый хеш - бери hashlib.

__eq__ без __hash__ (или наоборот) в своём классе-ключе. Равные объекты с разным хешем словарь «не узнает».

Доверять «возможно есть» как точному. Это ложноположительное с вероятностью p; перепроверяй.

Удалять из обычного фильтра Блума. Погасишь чужие биты → ложноотрицательные. Для удаления - счётный фильтр.

Взять слишком маленький m для своего n. Биты забьются, p подскочит к 100% (всегда «возможно есть»).

Проверь себя

Почему ключ словаря обязан быть неизменяемым?

Почему hash() строки разный между запусками и что из этого следует для кода?

Как фильтр Блума добавляет и проверяет элемент?

Почему у него нет ложноотрицательных, но есть ложноположительные, и почему нельзя удалять?

Сколько примерно бит на элемент нужно для p = 1% и почему ужать ошибку так дёшево?