Из чего состоит дикт в Python

Из чего состоит dict в Python

dict в Python — это хеш-таблица, которая состоит из массива бакетов (buckets) и использует хеширование для быстрого поиска, вставки и удаления элементов. Внутренняя реализация довольно сложная и оптимизирована.

История: две версии реализации

До Python 3.6 dict был просто хеш-таблицей. С Python 3.6+ dict сохраняет порядок вставки элементов благодаря новой реализации, которая более эффективна по памяти.

Основная структура хеш-таблицы

dict состоит из:

1. Массив бакетов (hash table) — основное хранилище индексов
2. Компактный массив записей (compact array) — хранит ключи, значения и хеши в порядке вставки
3. Функция хеширования — преобразует ключ в целое число

import sys

# Посмотреть размер dict
d = {"a": 1, "b": 2}
print(sys.getsizeof(d))  # 240 байт (пустой) или больше

# Посмотреть внутреннее состояние
print(d.__sizeof__())  # Размер самого dict

# Информация о размере таблицы
print(d.size if hasattr(d, 'size') else "Нет доступа")

Хеширование (Hashing)

Каждый ключ преобразуется в хеш — целое число:

# Встроенная функция hash()
key = "hello"
hash_value = hash(key)
print(f"Хеш '{key}': {hash_value}")

# Разные ключи имеют разные хеши (обычно)
print(hash("hello"))   # Одно значение
print(hash("hello"))   # Одно и то же значение (детерминированное)

# В одном запуске интерпретатора хеш один и тот же
keys = ["a", "b", "c"]
hashes = [hash(k) for k in keys]
print(hashes)

# Хеш для кортежей
print(hash((1, 2, 3)))  # Кортежи хешируемы
# print(hash([1, 2, 3]))  # Списки не хешируемы — TypeError!

# Кастомное хеширование
class Person:
    def __init__(self, name):
        self.name = name
    
    def __hash__(self):
        return hash(self.name)
    
    def __eq__(self, other):
        return self.name == other.name

p1 = Person("Иван")
p2 = Person("Иван")
print(hash(p1))       # Используется наш __hash__
print(p1 == p2)       # True
print(hash(p1) == hash(p2))  # True

# Используем объект как ключ
d = {p1: "Person 1"}
print(d[p2])  # Работает! "Person 1"

Коллизии и разрешение (Collision Resolution)

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

# Пример коллизии
class WeakHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        # Намеренно возвращаем одно и то же значение
        return 42
    
    def __eq__(self, other):
        return self.value == other.value
    
    def __repr__(self):
        return f"WeakHash({self.value})"

# Создаём коллизии
d = {}
for i in range(5):
    d[WeakHash(i)] = f"Value {i}"

print(d[WeakHash(2)])  # "Value 2" — всё равно находит правильное значение

Внутреннее представление (Python 3.6+)

Новая реализация dict разделяет данные на две части:

# Пример внутренней структуры (упрощённо):
# dict состоит из:
# 1. Hash table (массив малых индексов, указывающих на entries)
# 2. Entries array (массив {hash, key, value} в порядке вставки)

# В Python 3.6+ dict сохраняет порядок
d = {"z": 1, "a": 2, "m": 3}
for key in d:
    print(key)  # z, a, m — порядок сохранён!

# Это экономит ~20% памяти по сравнению со старой реализацией
import sys

d_small = {"a": 1}
d_large = {f"key_{i}": i for i in range(1000)}

print(f"Малый dict: {sys.getsizeof(d_small)} байт")
print(f"Большой dict: {sys.getsizeof(d_large)} байт")

Фактор загрузки и расширение

Когда dict становится слишком полным, он расширяется (rehashing):

# Python увеличивает размер таблицы при фактор загрузки > 2/3
# Это означает, что коллизии происходят редко

import sys

# Создаём dict и смотрим, как меняется размер
d = {}
for i in range(20):
    d[i] = i
    # Размер dict может внезапно увеличиться при достижении порога
    print(f"Элементов: {len(d)}, размер в памяти: {sys.getsizeof(d)}")

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

# Временная сложность операций dict:
# - Поиск (d[key]): O(1) в среднем
# - Вставка (d[key] = value): O(1) в среднем
# - Удаление (del d[key]): O(1) в среднем
# - Переход по элементам (for key in d): O(n)

import timeit

# Проверка O(1) поиска
d = {i: i for i in range(1000000)}

# Поиск в начале
time1 = timeit.timeit(lambda: d[0], number=1000000)
print(f"Поиск элемента 0: {time1:.4f}c")

# Поиск в конце
time2 = timeit.timeit(lambda: d[999999], number=1000000)
print(f"Поиск элемента 999999: {time2:.4f}c")

# Оба должны быть примерно одинаковы (O(1))

Оптимизация памяти: dict vs slots

class PersonWithDict:
    def __init__(self, name, age):
        self.__dict__["name"] = name
        self.__dict__["age"] = age

class PersonWithSlots:
    __slots__ = ['name', 'age']
    
    def __init__(self, name, age):
        self.name = name
        self.age = age

import sys

# Сравнение памяти
pd = PersonWithDict("Иван", 30)
ps = PersonWithSlots("Иван", 30)

print(f"С dict: {sys.getsizeof(pd.__dict__)} байт")
print(f"С __slots__: {sys.getsizeof(ps)} байт")

# __slots__ экономит память, но теряет гибкость
# ps.extra = 5  # AttributeError!

Особенности при использовании

# 1. Ключи должны быть хешируемы (immutable или с __hash__)
d = {}
d[(1, 2)] = "tuple key"  # ОК
# d[[1, 2]] = "list key"  # TypeError! Списки не хешируемы

# 2. Изменение ключа после добавления
key = [1, 2]  # Список
# d[key] = "value"  # TypeError

key = (1, 2)  # Кортеж
d[key] = "value"
# key = (1, 2, 3)  # Создаёт новый кортеж, не влияет на dict

# 3. Использование None как ключа
d = {None: "null value"}
print(d[None])  # "null value"

# 4. Удаление элемента
d = {"a": 1, "b": 2}
del d["a"]
print(d)  # {"b": 2}

# 5. Сохранение порядка (Python 3.7+ гарантирует)
d = {"z": 1, "a": 2}
list(d.keys())  # ["z", "a"] — порядок сохранён

Резюме

• Реализация: Hash table + compact array (Python 3.6+)
• Производительность: O(1) для поиска, вставки, удаления в среднем
• Коллизии: Разрешаются открытой адресацией
• Расширение: Происходит автоматически при фактор загрузки > 2/3
• Порядок: Сохраняется (Python 3.7+ гарантирует)
• Ключи: Должны быть хешируемыми и неизменяемыми
• Оптимизация: Для объектов используй slots вместо dict