Словари (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 — это результат многолетней оптимизации. Их реализация на основе хеш-таблиц с открытой адресацией, компактным хранением и защитой от атак делает их быстрыми и надежными. Понимание внутренней работы помогает:
- Избегать патологических сценариев (например, множества коллизий).
- Осознанно выбирать ключи (использовать хешируемые и неизменяемые типы).
- Оптимизировать код, работающий с большими объемами данных.