> Что происходит внутри dict при добавлении нового элемента (Python)

Короткий ответ

При добавлении нового элемента в dict Python вычисляет hash ключа, затем через маску (hash & mask) определяет индекс в массиве entries. Если слот свободен - вставляет пару ключ-значение. Если занят - происходит probing: последовательный поиск следующего свободного слота. При заполнении на 2/3 dict увеличивается в 4 раза (или в 2 раза для больших), пересчитываются индексы всех существующих элементов. Вставка в среднем O(1), в худшем - O(n).

Подробное объяснение

В CPython dict - это хеш-таблица с открытой адресацией. Внутренняя структура состоит из двух массивов:

1. indices - массив индексов (тип int32 или int64), размер - степень двойки.
2. entries - массив структур PyDictKeyEntry, содержащих hash, key, value.

Алгоритм вставки:

1. Вычисляется hash(key) - для строк и чисел это кэшированный хеш, для объектов - вызов __hash__.
2. Индекс в indices вычисляется как hash & mask, где mask = size - 1 (поэтому размер всегда степень двойки).
3. Если indices[index] пуст (значение -1), элемент записывается в entries на позицию used, а indices[index] получает этот номер.
4. Если слот занят, сравниваются хеши: если хеши равны, вызывается __eq__ для проверки равенства ключей. Если ключи равны - обновляется значение.
5. Если ключи не равны - начинается probing: линейно проверяются следующие слоты (index + 1, index + 2, ...) с учётом маски, пока не найдётся свободный или равный ключ.

Важные детали:

• Порог расширения: dict увеличивается, когда used * 3 >= size * 2 (заполнение 2/3). Это гарантирует, что probing остаётся коротким.
• Рост: при used < 50000 размер умножается на 4, иначе на 2. Новый размер - ближайшая степень двойки.
• Хранение хеша: хеш хранится в entries, поэтому при расширении не нужно пересчитывать хеши - только пересчитываются индексы.
• Кэширование хеша: для строк и чисел хеш вычисляется один раз и хранится в объекте, поэтому повторные вставки не требуют повторного вызова __hash__.

На практике

• Порядок вставки сохраняется с Python 3.7 (в CPython 3.6 как деталь реализации). Это достигается за счёт того, что entries - это массив в порядке вставки, а indices - только индексы.
• Удаление не сжимает таблицу сразу - помечает слот как "dummy" (-2), чтобы probing не сломался. Реальное сжатие происходит при расширении.
• Хеширование изменяемых ключей - критическая ошибка: если ключ изменится после вставки, dict сломается (нельзя будет найти элемент).
• Коллизии - основная причина деградации производительности. Плохой __hash__ (например, константа) превращает dict в связный список.

Пример кода

PYTHON
# Демонстрация влияния хеш-функции на производительность
import time

class BadHash:
    def __hash__(self):
        return 42  # все ключи в одну корзину

class GoodHash:
    def __hash__(self):
        return id(self)  # уникальный хеш

def measure(cls, n=10000):
    d = {}
    start = time.perf_counter()
    for i in range(n):
        d[cls()] = i
    return time.perf_counter() - start

print(f"BadHash: {measure(BadHash):.4f} сек")
print(f"GoodHash: {measure(GoodHash):.4f} сек")

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

Начни с краткого описания: хеш-таблица, вычисление индекса через маску, probing при коллизиях. Затем упомяни расширение при заполнении 2/3 и почему размер - степень двойки. Если спросят про порядок - объясни, что entries хранится отдельно от indices. Для middle-уровня достаточно этого. Если интервьюер углубляется - расскажи про dummy-слоты при удалении и кэширование хеша.

Что проверяет интервьюер

• Понимание базовой структуры хеш-таблицы: hash, mask, probing.
• Знание trade-off между памятью и скоростью (разреженная таблица ради O(1)).
• Осознание, почему порядок вставки сохраняется (отдельный массив entries).
• Понимание последствий плохой хеш-функции и изменяемых ключей.
• Умение объяснить, почему расширение происходит заранее (до полного заполнения).

Типичные ошибки

• Утверждение, что dict - это просто массив пар ключ-значение (без объяснения probing).
• Забывают про маску и степень двойки - говорят "деление по модулю".
• Не упоминают, что при расширении хеши не пересчитываются.
• Путают порядок: говорят, что порядок не гарантирован (это было до 3.7).
• Не знают про dummy-слоты при удалении - думают, что удаление просто обнуляет слот.
• Считают, что коллизии решаются через связные списки (это в Java HashMap, но не в CPython).