---
title: Хэш-функции
seo:
  title: Хэш-функции — Python Developer
  description: "Тема «Хэш-функции» для собеседования Python Developer. Как устроена хэш-таблица и почему поиск и вставка обычно занимают O(1), в том числе при расширении? Что такое хеширование и где оно применяется?"
---

[Все темы Python Developer](/python-developer)

## Как устроена хэш-таблица и почему поиск и вставка обычно занимают O(1), в том числе при расширении? [#q-14bee738d69b81089b42f3fae233c7fd]

Хэш-таблица хранит пары ключ–значение. Хэш-функция вычисляет числовой хэш ключа, а таблица использует его для выбора позиции. При коллизии ключи дополнительно сравниваются на равенство.

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

При расширении выделяется большая таблица и заново определяются позиции элементов. Саму хэш-функцию менять не обязательно: меняется отображение хэша в позицию. Например, CPython 3.14 при перестроении dict использует сохранённые хэши, а не вызывает заново пользовательский \_\_hash\_\_ для всех ключей.

При хорошем распределении и ограниченной загрузке поиск занимает ожидаемое O(1). Вставка имеет ожидаемую амортизированную сложность O(1): редкие расширения стоимостью порядка O(n) распределяются по серии вставок, если ёмкость растёт геометрически. Отдельная вставка с расширением не обязана быть O(1).

В худшем случае из-за коллизий поиск и вставка могут занимать O(n). Эти оценки предполагают O(1) для вычисления хэша и сравнения ключей; для длинных или пользовательских ключей их стоимость учитывается отдельно.

:::note[Ссылки для изучения]

1. [Хэш-функции в Python](https://ru.hexlet.io/courses/python-dicts/lessons/hash-table/theory_unit)
   :::

---

## Что такое хеширование и где оно применяется? [#q-14bee738d69b81669663d0cba38d9b40]

Хеширование преобразует данные в хэш фиксированного размера для выбранного алгоритма. Одинаковые данные дают одинаковый хэш при одних и тех же настройках, но одинаковый хэш не доказывает равенство данных: возможны коллизии.

В хэш-таблицах оно ускоряет поиск по ключу. Криптографические хэш-функции используются для проверки целостности и в схемах электронной подписи; их требования к стойкости отличаются от требований обычной хэш-таблицы. Хеширование не является шифрованием.

Для хранения паролей нужен специализированный медленный алгоритм с уникальной солью, например Argon2id. Обычный hash() или один быстрый SHA-256 для этого не подходят.

:::note[Ссылки для изучения]

1. [Хэш-функции в Python](https://ru.hexlet.io/courses/python-dicts/lessons/hash-table/theory_unit)
   :::