Что такое хеш-таблица и как работает dict в Python

Что такое хеш-таблица? Как работает словарь в Python внутри?

Хеш-таблица хранит пары ключ—значение и использует хеш-функцию, чтобы быстро находить место для ключа. Словарь dict в Python реализован как хеш-таблица: поиск, вставка и удаление в среднем выполняются за O(1), но ключи должны быть хешируемыми.

Подробный ответ

Что такое хеш-таблица

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

user = {
    'id': 42,
    'name': 'Alex',
}

print(user['name'])
user['role'] = 'admin'

Как работает dict в Python

При обращении к dictionary[key] Python вычисляет hash(key) и использует результат для поиска записи во внутренней хеш-таблице. Если разные ключи имеют конфликтующий хеш или попадают в одну область таблицы, Python сравнивает ключи, чтобы найти нужный.

Коллизии

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

Сложность операций

Операция	Средняя сложность	Худший случай
Получение по ключу	`O(1)`	`O(n)`
Вставка	`O(1)`	`O(n)`
Удаление	`O(1)`	`O(n)`
Проверка ключа через in	`O(1)`	`O(n)`

Хешируемые ключи

Ключ словаря должен быть хешируемым, то есть его хеш не должен меняться в течение жизни объекта. Поэтому строки, числа и кортежи из неизменяемых значений могут быть ключами, а список и обычный словарь — нет.

valid = {
    'name': 'Alex',
    42: 'answer',
    ('ru', 'en'): 'translation',
}

# invalid = {[1, 2]: 'value'}

Как ответить на собеседовании

Хеш-таблица хранит пары ключ—значение и через hash ключа быстро находит нужную запись. Python dict реализован как хеш-таблица, поэтому поиск, вставка и удаление в среднем имеют сложность O(1). Коллизии возможны, но внутренняя реализация их разрешает; ключи должны быть хешируемыми и неизменяемыми по смыслу.