Конспект раздела: хеширование

Карта раздела

Раздел отвечает на вопрос «как получить доступ по ключу за O(1) и чего это стоит». Четыре главы - от идеи хеш-функции до вероятностного фильтра.

хеш-функция и коллизии   ->  ключ → номер ячейки за O(1); коллизии неизбежны
     |                        (Дирихле, парадокс дней рождения); α = n/m
разрешение коллизий      ->  цепочки (1+α) vs открытая адресация (1/(1−α));
     |                        надгробия, кластеризация, локальность памяти
универсальное/идеальное  ->  случайная функция из семейства (ожидание, защита от HashDoS);
     |                        идеальное - O(1) в худшем для статичного набора
на практике              ->  dict настоящего языка; фильтр Блума (точно нет / возможно есть)

Сквозная мысль: хеш-таблица - это O(1) в СРЕДНЕМ, и весь раздел о том, что стоит за этой оговоркой (коллизии, α, злой вход) и как её укрепляют.

Главные величины и формулы

величина	смысл
`α = n/m`	коэффициент заполнения (теснота)
коллизия при `n > m`	гарантирована (Дирихле)
коллизия при `n ≈ √m`	вероятна (парадокс дней рождения)
цепочки: поиск	`≈ 1 + α`
открытая адресация: неудачный поиск, равномерное хеширование	`≈ 1/(1 − α)` (нужен `α < 1`)
универсальность	`Pr[h(k₁)=h(k₂)] ≤ 1/m`
идеальное: вторичка	размер `k²`, память суммарно `O(n)`
фильтр Блума: память	`≈ 1.44·log₂(1/p)` бит на элемент
фильтр Блума: функций	`k ≈ 0.69·m/n`

Дерево решений: словарь, дерево или фильтр

Главный практический итог - выбрать структуру под задачу.

Нужен доступ по ключу?
├─ Нужен ТОЧНЫЙ ответ и значения по ключу?
│   ├─ Порядок ключей / диапазонные запросы / гарантия O(log n) в худшем? → ДЕРЕВО поиска
│   │                                                       (следующий раздел)
│   └─ Порядок не нужен, хватает O(1) в среднем? → ХЕШ-ТАБЛИЦА (dict / set)
│       ├─ набор СТАТИЧЕН и нужна гарантия O(1) в худшем? → идеальное хеширование
│       └─ вход недоверенный (защита от HashDoS)? → универсальное (соль)
└─ Нужна лишь проверка НАЛИЧИЯ, элементов ОЧЕНЬ много, память дорога,
    и ответ «точно нет» экономит дорогую проверку? → ФИЛЬТР БЛУМА
        (доверяй «нет», «возможно» перепроверяй)

Коротко: хеш-таблица - доступ по ключу за O(1) в среднем, без порядка; дерево поиска - O(log n) в худшем И порядок/диапазоны (следующий раздел); фильтр Блума - почти бесплатная по памяти проверка наличия с односторонней ошибкой.

Ключевые компромиссы

O(1) в среднем, не в худшем. Хеш-таблица быстра в среднем, но коллизии, рехеширование и плохая функция дают O(n)-всплески. Где нужен гарантированный худший случай или порядок - дерево.

Цепочки vs открытая адресация. До α ≈ 0.7 оба быстры, открытая адресация выигрывает по кешу (локальность); выше - 1/(1−α) взрывается, цепочки терпят. Держи α низким.

Случайность как броня. Универсальное хеширование - случайный выбор функции из универсального семейства, а не просто соль, - защищает от подобранного входа - тот же приём, что рандомизация опорного в выборе k-го.

Знание о входе → сильнее гарантия. Статичный набор → идеальное хеширование (O(1) в худшем). Как «знаешь диапазон - сортируешь за линию».

Точность за память. Фильтр Блума жертвует точностью ответа «да» ради колоссальной экономии памяти на массовых «нет».

Ловушки джокера всего раздела

m = степень двойки на закономерных данных - перекос в пару ячеек. Бери простое.

«Возьму таблицу с запасом - коллизий не будет» - при α = 0.5 их сотни (парадокс дней рождения).

Заполнил открытую адресацию под завязку - 1/(1−α) взрывается, вставка невозможна.

Удалил из открытой адресации, опустошив ячейку - порвал цепочку проб. Нужны надгробия.

Изменяемый объект как ключ словаря - потеряется при изменении (хеш уедет).

Доверяешь «возможно есть» фильтра Блума как точному - это ложноположительное, перепроверяй.

Проверь себя

Почему коллизии неизбежны и что задаёт скорость хеш-таблицы?

Чем цепочки отличаются от открытой адресации и когда какой способ брать?

Что такое универсальное хеширование и от чего оно защищает?

Чем идеальное хеширование отличается от универсального и при каком условии применимо?

Когда брать хеш-таблицу, когда дерево, а когда фильтр Блума?