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

Понятия

Атака на фиксированную функцию (HashDoS) - зная публичную хеш-функцию, противник подбирает ключи с одним h(k), валит их в одну ячейку, и операции становятся O(n). Реально клали веб-сервисы горстью подобранных параметров.

Универсальное хеширование - берут СЕМЕЙСТВО функций H и выбирают СЛУЧАЙНУЮ при создании таблицы (случайность в тайных параметрах, например a, b). Семейство универсально, если Pr[h(k₁) = h(k₂)] ≤ 1/m для любых k₁ ≠ k₂ (по выбору h). Даёт ожидаемую длину цепочки 1 + α на ЛЮБОМ входе: враг знает семейство, но не выбранную функцию. Это O(1) в ОЖИДАНИИ, не гарантия. Годится для ДИНАМИЧЕСКОГО набора.

Идеальное хеширование - O(1) в ХУДШЕМ случае и память O(n), но только для СТАТИЧНОГО набора (известен заранее). Два уровня: - уровень 1: универсальная функция раскидывает n ключей по n корзинам (коллизии есть); - уровень 2: корзину из kⱼ ключей кладут во вторичную таблицу размером kⱼ² со своей функцией БЕЗ коллизий.

Размер k² - из парадокса дней рождения наоборот: при m = k² ожидаемых коллизий ≈ 1/2, бескризисную функцию находят за пару попыток. Сумма Σ kⱼ² = O(n) (универсальная верхняя функция не создаёт больших корзин).

Что унести

Два инструмента под два условия - и общий принцип «гарантии покупаются знанием о входе».

Универсальное хеширование - это тот же приём, что рандомизация опорного в выборе k-го: детерминированный алгоритм уязвим к подобранному входу → добавь случайность ВНУТРЬ, и источник неудачи переедет с данных (их контролирует враг) на монетку (её контролируешь ты). Поэтому языки солят хеш строк случайным семенем при старте (Python PYTHONHASHSEED) - hash("...") меняется между запусками, и это защита, а не баг.

Идеальное хеширование показывает вторую мысль: чем больше знаешь о входе ЗАРАНЕЕ (набор статичен), тем сильнее гарантию можно выжать (O(1) в худшем, а не только в среднем). Тот же мотив, что «знаешь диапазон ключей - сортируешь за линию».

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

Фиксированная публичная функция для недоверенного входа (HTTP-параметры, имена от пользователя). Открыт путь к HashDoS. Нужна соль/универсальное хеширование.

Выбор случайной функции на КАЖДУЮ операцию. Один ключ попадёт в разные ячейки - не найдёшь. Функция выбирается ОДИН раз при создании.

«Универсальное = гарантия в худшем случае». Нет, это ОЖИДАНИЕ. Гарантию даёт идеальное (для статики).

Идеальное хеширование для динамического набора. Добавление ключа ломает бескризисность, нужна перестройка. Только статика.

Вторичная таблица размером k вместо k². Коллизии вернутся (α = 1). Нужен квадрат.

Испуг «память O(n²)». При универсальной верхней функции Σ kⱼ² = O(n); не повезло - перевыбрать функцию.

Проверь себя

Почему фиксированную функцию можно атаковать и что такое HashDoS?

Что такое универсальное семейство (определение через Pr ≤ 1/m) и почему оно защищает даже знающего семейство врага?

Чем «ожидаемо O(1)» отличается от «гарантированно O(1)»?

Как устроены два уровня идеального хеширования и почему второй берут размером k²?

Почему суммарная память идеального хеширования O(n), а не O(n²)?