Как устроены дикты в Python?

Устройство словарей в Python

Словари (dictionaries) — это одна из самых быстрых и универсальных структур данных в Python. Их реализация использует хеширование и требует глубокого понимания для оптимизации производительности.

1. Основной механизм: хеш-таблица

Внутри Python словарь реализуется как динамическая хеш-таблица:

import sys

d = {'a': 1, 'b': 2}
print(sys.getsizeof(d))  # размер в памяти
print(d.__sizeof__())     # альтернативный способ

Каждый ключ преобразуется в хеш-код через функцию hash(key), который определяет позицию в массиве:

hash('hello')     # -5363270541405537893
hash(42)          # 42
hash((1, 2))      # -3550055990210131217
hash({'a': 1})    # TypeError - dict unhashable

2. Коллизии и разрешение

Когда два разных ключа имеют одинаковый хеш, возникает коллизия. Python использует открытую адресацию (linear probing):

# Упрощённый алгоритм поиска
def lookup(hash_table, key):
    hash_code = hash(key)
    index = hash_code % len(hash_table)
    
    while hash_table[index] is not None:
        if hash_table[index][0] == key:
            return hash_table[index][1]
        # Линейное пробирование - переходим к следующей ячейке
        index = (index + 1) % len(hash_table)
    
    raise KeyError(key)

3. Фактор загрузки и пересчёт размера

Когда словарь заполняется, Python автоматически увеличивает размер таблицы (обычно в 4 раза):

d = {}
for i in range(1000):
    d[i] = i
    # При достижении порога (примерно 2/3 заполнения)
    # словарь перестраивается с новым размером

Исторические размеры таблицы в CPython:

• 8 (начальный)
• 32 (после первого пересчёта)
• 128, 512, 2048, 8192...

4. Компактная реализация (CPython 3.6+)

С Python 3.6 словари более эффективны по памяти, используя индексный массив:

import sys

d = {'name': 'Alice', 'age': 30, 'city': 'New York'}
print(sys.getsizeof(d))  # ~240 байт (не зависит от кол-ва элементов!)

# Структура:
# 1. Индексный массив - быстрый поиск по хешу
# 2. Массив пар (ключ, значение) - линейное хранилище
# 3. Хешмасп - маппинг хешей на индексы

5. Порядок элементов

После Python 3.7 словари гарантированно сохраняют порядок вставки:

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

# Это требование закреплено в spec, а не просто реализация
for key in d:  # итерация в порядке добавления
    print(key, d[key])

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

Ключи должны быть хешируемыми (immutable):

# Валидные ключи
d = {
    'string': 1,        # строка
    42: 'int',          # число
    (1, 2, 3): 'tuple', # кортеж
    True: 'bool',       # булево (True == 1)
}

# Невалидные ключи
# d[[1, 2, 3]] = 'list'     # TypeError
# d[{'a': 1}] = 'dict'      # TypeError
# d[{1, 2}] = 'set'         # TypeError

7. Сложность операций

d = {k: v for k, v in enumerate(range(1000000))}

# Операции и сложность:
d['key']              # O(1) в среднем, O(n) в худшем (много коллизий)
d['key'] = value      # O(1) в среднем
del d['key']          # O(1) в среднем
key in d              # O(1) в среднем
d.get('key')          # O(1) в среднем

8. Внутренние флаги и состояние

d = {'a': 1, 'b': 2}
print(d.__sizeof__())     # текущий размер в памяти

# CPython хранит:
# - размер таблицы
# - кол-во элементов
# - версионный номер (для оптимизации доступа)
# - флаги (является ли класс или инстанс)

9. Оптимизация использования

# Плохо - частое пересоздание
for key in keys:
    d = {}  # каждый раз новая таблица
    d[key] = value

# Хорошо - один раз создали, используем
d = {}
for key in keys:
    d[key] = value

# Предварительное выделение (если известен размер)
from collections import defaultdict
d = {k: None for k in range(100)}  # рациональное использование памяти

10. Сравнение с другими структурами

Ключевые выводы

• Словари используют хеш-таблицы с открытой адресацией
• Операции в среднем O(1), но требуют хешируемых ключей
• Python 3.7+ гарантирует порядок вставки
• При заполнении таблица автоматически расширяется
• Коллизии редки благодаря хорошей распределение хешей
• Компактная реализация с Python 3.6+ экономит память