Какая структура данных лежит в основе dict в Python?

Структура данных dict в Python: Hash Table

Основа: Hash Table (Хеш-таблица)

Dict в Python реализован как динамическая хеш-таблица. Это одна из самых важных структур данных, обеспечивающая быстрый поиск, вставку и удаление за O(1) в среднем случае.

Как работает хеш-таблица?

# Внутренно Python примерно так обрабатывает операции:
d = {}
d["key"] = "value"

# Этапы:
# 1. Вычислить хеш ключа: hash("key") = 12416037344 (пример)
# 2. Найти индекс в массиве: index = hash("key") % size
# 3. Если место свободно: вставить (key, value)
# 4. Если занято: разрешить коллизию (в Python3 используется open addressing)

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

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

# Если index занят, пробуем следующие индексы
index = hash(key) % size
for i in range(1, size):
    index = (hash(key) + i*i) % size  # Квадратичное смещение
    if table[index] is empty:
        insert here
        break

Внутренняя структура в Python 3.6+

В Python 3.6+ dict реализован с использованием компактного массива индексов + массива записей:

┌─────────────────────────────────────────┐
│ Компактный индексный массив (малый)     │  ← быстро найти индекс
│ [0, 1, _, 2, _,3, ...]                  │
└─────────────────────────────────────────┘
         ↓
┌─────────────────────────────────────────┐
│ Массив записей (только использованные) │  ← компактное хранение
│ [0]: (a, 10)                          │
│ [1]: (b, 20)                          │
│ [2]: (c, 30)                          │
└─────────────────────────────────────────┘

Это позволяет:

• Сохранять порядок вставки (insertion order)
• Экономить память (не тратить место на пустые слоты)
• Быстро перебирать элементы

Временная сложность операций

# Все эти операции работают за O(1) в среднем случае:
d[key] = value        # Вставка/обновление - O(1)
value = d[key]        # Поиск - O(1)
del d[key]            # Удаление - O(1)
key in d              # Проверка наличия - O(1)

# O(n) операции:
len(d)                # O(1) в Python 3 (сохраняется счётчик)
d.items()             # O(n) - перебор всех элементов

Коэффициент загрузки и расширение

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

# Python автоматически увеличивает размер массива,
# когда коэффициент загрузки превышает ~2/3

load_factor = num_elements / table_size
if load_factor > 2/3:
    # Создать новую таблицу большего размера (обычно 4x)
    # Перехешировать все ключи
    # Скопировать элементы

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

Почему нужна хеш-функция?

# Хеш-функция преобразует объект в число
hash("hello")        # -6969068721951701079
hash(123)            # 123
hash((1, 2, 3))      # -9223372036854775794

# Объект должен быть hashable (неизменяемый):
hash([1, 2, 3])      # TypeError! Списки изменяемые

# Изменяемые типы не могут быть ключами:
my_dict = {[1, 2]: "value"}  # ❌ TypeError
my_dict = {(1, 2): "value"}   # ✅ OK - кортеж неизменяемый

Особенности хеш-таблицы в Python

• Сохранение порядка (с Python 3.7 это гарантировано)
• Динамическое расширение при необходимости
• Хеш рандомизация для защиты от DoS атак (PYTHONHASHSEED)
• Оптимизация памяти через компактное представление

Практический пример

# Быстрая работа со множеством данных
data = {i: f"value_{i}" for i in range(1000000)}

# Все эти операции быстрые благодаря хеш-таблице:
if 500000 in data:              # O(1)
    value = data[500000]         # O(1)
    del data[500000]             # O(1)

# В отличие от списка, где поиск O(n):
data_list = list(range(1000000))
if 500000 in data_list:          # O(n) - медленно!

Заключение

Dict в Python — это оптимизированная хеш-таблица с open addressing, которая обеспечивает быстрый доступ, сохраняет порядок вставки и эффективно использует память. Это одна из причин, почему Python так популярен для анализа данных и ML.