1. Хеш-таблицы: основа словарей

1. Хеш-таблицы: основа словарей

Техническая реализация словарей (dict) в Python: как это работает под капотом

Словари (dict) — одна из самых оптимизированных структур данных в Python. Их скорость и гибкость достигаются за счет продуманной внутренней реализации на основе хеш-таблиц. В этой статье мы разберем, как устроены словари в CPython (стандартной реализации Python), как они хранят данные, обрабатывают коллизии и обеспечивают константное время доступа O(1) в среднем случае.

1. Хеш-таблицы: основа словарей

Словарь в Python — это хеш-таблица, которая состоит из массива “ведер” (buckets). Каждое ведро хранит:

  • Хеш ключа (hash),
  • Ключ (key),
  • Значение (value).

При добавлении элемента:

  1. Вычисляется хеш ключа через встроенную функцию hash().
  2. На основе хеша определяется индекс ведра в массиве.
  3. Если ведро пустое — данные сохраняются в него.
  4. Если ведро занято — возникает коллизия, и система ищет следующее свободное ведро по определенному алгоритму.

2. Разрешение коллизий: метод открытой адресации

В Python для разрешения коллизий используется открытая адресация (open addressing), а не связные списки (как в некоторых других языках).
Алгоритм поиска свободного ведра:

  1. Вычисляется стартовый индекс: index = hash(key) % table_size.
  2. Если ведро занято, проверяется следующее по формуле:
    new_index = (5 * index + 1 + perturb) % table_size,
    где perturb — вспомогательная переменная для псевдослучайного смещения (чтобы избежать кластеризации).

Пример поиска места для ключа "name":

hash("name") = 123456789
index = 123456789 % 8 = 5  # Предположим, размер таблицы 8
# Если ведро 5 занято, проверяем 5 + 1, затем 5 + 6 и т.д.

3. Структура хеш-таблицы в CPython

Начиная с Python 3.6, реализация словарей была оптимизирована для экономии памяти. Теперь данные хранятся в двух массивах:

  1. Индексный массив (indices):
    Содержит индексы (номера) записей в основном массиве.
    Размер: степень двойки (например, 8, 16, 32).
  2. Основной массив (entries):
    Хранит структуры PyDictKeyEntry, включающие хеш, ключ и значение.
    Порядок элементов соответствует порядку их добавления (поэтому словари сохраняют порядок в Python 3.7+).

Пример структуры:

struct PyDictKeyEntry {
    Py_hash_t hash;  // Хеш ключа
    PyObject* key;    // Указатель на ключ
    PyObject* value;  // Указатель на значение
};

4. Процесс вставки элемента

Рассмотрим пример вставки пары "name": "Anna":

  1. Вычисляется хеш ключа: hash("name").
  2. Определяется индекс в индексном массиве: hash % indices_size.
  3. Если индекс свободен:
    • В основной массив добавляется новая запись.
    • В индексном массиве сохраняется индекс этой записи.
  4. Если индекс занят (коллизия):
    • Поиск следующего свободного места в индексном массиве.
    • Обновление основной записи или создание новой.

5. Удаление элемента

При удалении элемента:

  1. Находится соответствующая запись в основном массиве.
  2. Значение помечается как удаленное (dummy), чтобы не нарушать цепочки поиска при коллизиях.
  3. При последующих вставках “удаленные” ведра могут быть переиспользованы.

6. Изменение размера таблицы

Хеш-таблица динамически расширяется при заполнении.
Правило: если таблица заполнена на 2/3, она увеличивается в 2–4 раза.
При этом:

  • Создается новый индексный массив большего размера.
  • Все существующие элементы перехэшируются и перераспределяются.

Пример:

  • Исходный размер: 8 ведер.
  • При добавлении 6-го элемента (6/8 = 0.75 ≥ 2/3) размер увеличивается до 16.

7. Защита от атак через коллизии

В Python (с версии 3.3+) используется рандомизация хешей (Hash randomization):

  • При запуске интерпретатора генерируется случайное число (PYTHONHASHSEED), которое добавляется к хешам строк и некоторых других объектов.
  • Это предотвращает атаки, когда злоумышленник создает множество ключей с одинаковыми хешами, чтобы замедлить работу словаря.

8. Пример: как работает поиск элемента

Рассмотрим словарь d = {"a": 1, "b": 2}:

  1. Хеш "a" = 1245, "b" = 5678.
  2. Размер индексного массива = 8.
  3. Индексы:
    • "a" → 1245 % 8 = 5
    • "b" → 5678 % 8 = 2
  4. Основной массив хранит записи в порядке добавления: 
    entries = [
    (hash("a"), "a", 1),
    (hash("b"), "b", 2)
]
  5. Индексный массив: 
    indices = [None, None, 1, None, None, 0, None, None]
# indices[5] → 0 (первая запись), indices[2] → 1 (вторая запись)

9. Оптимизации в CPython

  • Compact Dictionaries (Python 3.6+):
    Основной массив хранит записи в порядке добавления, что позволяет быстро итерировать по словарю.
  • Shared Keys (Python 3.3+):
    Словари с одинаковым набором ключей могут разделять метаданные, экономя память.
  • Caching Хешей:
    Для часто используемых ключей (например, строк) хеши кэшируются, чтобы избежать повторных вычислений.

10. Производительность: когда словарь замедляется

  • Высокий коэффициент заполнения (близкий к 2/3): увеличивается количество коллизий.
  • Большое количество удалений: множество “удаленных” меток замедляет поиск.
  • Слабые хеш-функции: если хеши ключей плохо распределены, коллизии учащаются.

11. Как посмотреть внутреннюю структуру словаря

Стандартный Python не предоставляет API для доступа к внутренним массивам словаря, но можно использовать модуль gc или C-расширения. Пример через gc (для образовательных целей):

import gc

d = {"a": 1, "b": 2}
# Получаем список объектов-словарей
for obj in gc.get_objects():
    if isinstance(obj, dict) and obj == d:
        print("Dict internals:", obj.__dict__)

Заключение

Словари в Python — это результат многолетней оптимизации. Их реализация на основе хеш-таблиц с открытой адресацией, компактным хранением и защитой от атак делает их быстрыми и надежными. Понимание внутренней работы помогает:

  • Избегать патологических сценариев (например, множества коллизий).
  • Осознанно выбирать ключи (использовать хешируемые и неизменяемые типы).
  • Оптимизировать код, работающий с большими объемами данных.