Объясните, как работает словарь Python изнутри. Какие стратегии он использует для обработки коллизий хешей?

Подсказки:

• Подумайте, как словари хранят пары ключ-значение внутри.
• Подумайте о временной сложности операций со словарями и о том, почему они такие эффективные.
• Возможно, стоит обсудить подходы к разрешению коллизий с open addressing и chaining.

Выше ожиданий:

• Сохранение порядка словарей с Python 3.7.
• Реализация деталей PyDictObject в CPython.
• Пороговое значение коэффициента заполнения, которое запускает изменение размера.

Структура хеш-таблицы

Тип dict в Python реализован как хеш-таблица (также называемая hash map), что обеспечивает среднее время выполнения операций поиска, вставки и удаления O(1). Хеш-таблица состоит из:

1. Массива "слотов" или "бакетов"
2. Хеш-функции для преобразования ключей в индексы массива
3. Механизма разрешения коллизий

Внутренняя реализация словарей в CPython (реализации Python по умолчанию) — это структура данных PyDictObject. Эта структура поддерживает:

• Массив записей, каждая из которых содержит хеш-значение, указатель на ключ и указатель на значение.
• Метаданные о размере и емкости.
• Специальные механизмы для повышения эффективности использования памяти.

Хеш-функция и индексирование

При добавлении пары ключ-значение в словарь Python:

1. Вычисляется хеш ключа с помощью метода __hash__().
2. Это хеш-значение используется для определения, в какой бакет следует поместить запись.
3. Запись помещается в этот бакет или обрабатываются коллизии, если необходимо.

Каждый хешируемый объект Python имеет хеш-значение, вычисленное его методом __hash__(). Например:

hash("hello")  # Возвращает согласованное целочисленное хеш-значение

Вычисленное хеш-значение затем маскируется битовой маской, чтобы поместиться в размер хеш-таблицы.

Разрешение коллизий

Словари Python используют open addressing с probing для разрешения коллизий. При возникновении коллизии:

1. Алгоритм вычисляет дополнительное значение "возмущения" (perturb) из исходного хеша.
2. Он использует это значение для перехода к другой позиции в массиве.
3. Этот процесс продолжается до тех пор, пока не будет найдена пустая ячейка или сам ключ.

Python behind the scenes #10: how Python dictionaries work

def get_probes(hash_value, hash_table_size):
    mask = hash_table_size - 1 # used to take modulus fast
    perturb = hash_value # used to perturb the probe sequence
    probe = hash_value & mask

    while True:
        yield probe

        perturb >>= 5
        probe = (probe * 5 + perturb + 1) & mask

Изначально, perturb устанавливается равным хеш-значению. Затем, на каждой итерации, он сдвигается на 5 бит вправо, и результат добавляется к линейному конгруэнтному генератору для возмущения следующего пробирования. Таким образом, каждое следующее пробирование зависит от дополнительных 5 бит хеша, пока perturb не станет равным 0. Когда perturb становится 0, линейный конгруэнтный генератор гарантированно охватывает все бакеты согласно теореме Халла-Добелла.

Этот подход позволяет избежать необходимости в связанных списках, которые использовались бы при разрешении коллизий.

Коэффициент заполнения и изменение размера

Словари Python отслеживают свой коэффициент заполнения (отношение используемых записей к общему размеру) и запускают изменение размера, когда он превышает порог (приблизительно 2/3 или 0.66). При изменении размера:

1. Выделяется новый массив большего размера (обычно в 2-3 раза больше).
2. Все существующие пары ключ-значение перехешируются и вставляются в новый массив.
3. Старый массив отбрасывается.

Это амортизирует затраты на изменение размера во многих операциях, поддерживая среднее время выполнения O(1).

Сохранение порядка

Начиная с Python 3.7, словари сохраняют порядок вставки. Это было реализовано:

1. Через поддержание отдельного связанного списка записей в порядке вставки.
2. Гарантируя, что итерация следует этому связанному списку, а не бакетам хеш-таблицы.

Эта функция изначально была реализована как оптимизация CPython, но стала официальной языковой функцией из-за своей полезности.

Оптимизация памяти

Реализация словарей Python включает несколько оптимизаций памяти:

• Для небольших словарей (менее 8 записей) используется компактное представление.
• Словари общих ключей для экземпляров классов для уменьшения использования памяти.
• Один массив ключей может быть совместно использован между несколькими массивами значений.

Поведение пустого словаря

Пустой словарь в Python начинает с небольшой емкости (обычно 8 записей) и увеличивается по мере необходимости. Это минимизирует использование памяти для простых небольших словарей, часто создаваемых в программах Python.