Как устроен словарь под капотом?

Устройство словаря (dict) в Python

Словарь в Python — это одна из самых важных и оптимизированных структур данных. Понимание её внутреннего устройства критично для эффективного кода.

Основные компоненты

На самом деле, dict в Python реализован как hash table (хеш-таблица). Вот как это работает:

# Словарь — это коллекция пар ключ-значение
my_dict = {"name": "Alice", "age": 30, "city": "Moscow"}

# Под капотом хранится хеш каждого ключа
print(hash("name"))  # Пример: 8765432109876543210

Алгоритм работы

Шаг 1: Хеширование ключа Когда ты обращаешься к элементу, Python вычисляет хеш ключа:

key = "name"
hash_value = hash(key)  # Вычисляется хеш
index = hash_value % len(hash_table)  # Находится индекс в таблице

Шаг 2: Разрешение коллизий Если два разных ключа имеют одинаковый индекс (коллизия), используется open addressing (открытая адресация):

# Если позиция занята, ищем следующую свободную
# Используется последовательность проб
index = (hash_value + probe_offset) % table_size

Шаг 3: Сохранение и доступ В каждой позиции хранится пара (ключ, значение):

# Внутренняя структура выглядит примерно так:
hash_table = [
    None,                    # [0] пусто
    ("name", "Alice"),       # [1] ключ + значение
    ("age", 30),            # [2] ключ + значение
    None,                    # [3] пусто
    ("city", "Moscow"),     # [4] ключ + значение
]

Требования к ключам

Ключи должны быть хешируемыми — у них должен быть неизменяемый хеш-код:

# ✅ Валидные ключи (хешируемые)
d = {
    42: "number",
    "key": "string",
    (1, 2, 3): "tuple",
    frozenset([1, 2]): "frozenset",
    None: "none_value"
}

# ❌ Невалидные ключи (unhashable)
d = {
    [1, 2, 3]: "list"     # TypeError: unhashable type: 'list'
}

Эффективность операций

# O(1) в среднем случае
d = {"a": 1, "b": 2, "c": 3}

d["a"]          # O(1) доступ
d["d"] = 4      # O(1) вставка
del d["a"]      # O(1) удаление
"a" in d        # O(1) проверка наличия

# O(n) в худшем случае (много коллизий)
# Но это редко при хорошей функции хеширования

Resizing (переразмеров)

Когда таблица заполняется на определённый процент (~66%), Python перестраивает таблицу с большим размером:

# Упрощённо:
if len(dict) > load_factor * table_size:
    new_table_size = table_size * 2  # или больше
    rehash_all_items()               # пересчитываем индексы
    table = new_table                # меняем таблицу

Это эффективно благодаря амортизированной сложности O(1).

Порядок элементов (Python 3.7+)

Начиная с Python 3.7, словари сохраняют порядок вставки:

d = {"z": 1, "a": 2, "m": 3}
print(list(d.keys()))  # ['z', 'a', 'm'] — в порядке вставки

# Это реализовано через дополнительный массив индексов
# insertion_order = [z_index, a_index, m_index]

Оптимизация ключей словаря

В CPython 3.6+ есть оптимизация для словарей с строковыми ключами (как в locals() и globals()):

# Компактное представление для параметров функций
def func(name, age, city):
    pass  # locals() здесь эффективнее обычного dict

Практические примеры оптимизации

# ❌ Плохо: много проверок наличия ключа
for key in many_keys:
    if key in d:
        value = d[key]
    else:
        value = default

# ✅ Хорошо: используем get()
for key in many_keys:
    value = d.get(key, default)

# ✅ Хорошо: используем setdefault()
d.setdefault(key, default_value)

# ✅ Хорошо: используем defaultdict
from collections import defaultdict
d = defaultdict(int)
d[key] += 1  # Автоматически инициализирует нулём

Итоги

• Hashing: каждый ключ хешируется для быстрого доступа
• Open addressing: разрешение коллизий
• O(1) операции: в среднем для доступа и вставки
• Resizing: автоматическое переразмеривание при нужде
• Порядок: сохраняется с Python 3.7+