Что делает хеш-функцию хорошей и что такое атака HashDoS?

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

Свойства хорошей функции

• Использует все биты ключа: хеш строки только по первым символам даст массовые коллизии.
• Лавинный эффект: изменение одного бита входа меняет около половины битов выхода.
• Скорость важнее криптостойкости: SHA-256 для хеш-таблицы избыточно медленный.

Пример плохой функции

String.hashCode в Java — полином с основанием 31, и коллизии легко строятся вручную:

const javaHash = (s) =>
  [...s].reduce((h, c) => (h * 31 + c.charCodeAt(0)) | 0, 0);

javaHash("Aa") === javaHash("BB"); // true, оба 2112
// склейки "AaAa", "AaBB", "BBAa", "BBBB" тоже совпадают

HashDoS и защита

• В 2011 году показали атаку на веб-фреймворки: один POST-запрос с тысячами коллидирующих параметров загружал CPU на минуты.
• Рандомизированный сид на процесс: Python включил его по умолчанию в 3.3.
• Ключевые PRF вроде SipHash — в Python для строк, в Rust HashMap по умолчанию.
• Деревья в корзинах: Java 8 превращает длинную цепочку в красно-чёрное дерево.
• Лимиты на число параметров запроса.

Коротко для собеседования

Для хеш-таблиц нужна быстрая функция с равномерным распределением, а не криптографическая. Если ключи приходят извне, предсказуемый хеш позволяет завалить сервис коллизиями, поэтому языки используют ключевую функцию вроде SipHash со случайным сидом — MurmurHash с сидом от этого не спасает.