Хэш-функции
Как устроена хэш-таблица и почему поиск и вставка обычно занимают O(1), в том числе при расширении?
Хэш-таблица хранит пары ключ–значение. Хэш-функция вычисляет числовой хэш ключа, а таблица использует его для выбора позиции. При коллизии ключи дополнительно сравниваются на равенство.
Для хэш-таблицы важны быстрое вычисление и хорошее распределение хэшей. Равные ключи должны иметь одинаковый хэш; хэш ключа не должен меняться, пока ключ находится в таблице. Разные ключи могут иметь одинаковые хэши, поэтому обработка коллизий обязательна. Криптографическая стойкость для обычной таблицы не требуется.
При расширении выделяется большая таблица и заново определяются позиции элементов. Саму хэш-функцию менять не обязательно: меняется отображение хэша в позицию. Например, CPython 3.14 при перестроении dict использует сохранённые хэши, а не вызывает заново пользовательский __hash__ для всех ключей.
При хорошем распределении и ограниченной загрузке поиск занимает ожидаемое O(1). Вставка имеет ожидаемую амортизированную сложность O(1): редкие расширения стоимостью порядка O(n) распределяются по серии вставок, если ёмкость растёт геометрически. Отдельная вставка с расширением не обязана быть O(1).
В худшем случае из-за коллизий поиск и вставка могут занимать O(n). Эти оценки предполагают O(1) для вычисления хэша и сравнения ключей; для длинных или пользовательских ключей их стоимость учитывается отдельно.
Что такое хеширование и где оно применяется?
Хеширование преобразует данные в хэш фиксированного размера для выбранного алгоритма. Одинаковые данные дают одинаковый хэш при одних и тех же настройках, но одинаковый хэш не доказывает равенство данных: возможны коллизии.
В хэш-таблицах оно ускоряет поиск по ключу. Криптографические хэш-функции используются для проверки целостности и в схемах электронной подписи; их требования к стойкости отличаются от требований обычной хэш-таблицы. Хеширование не является шифрованием.
Для хранения паролей нужен специализированный медленный алгоритм с уникальной солью, например Argon2id. Обычный hash() или один быстрый SHA-256 для этого не подходят.