Как устроен словарь в Python? Какова сложность доступа к элементу по ключу?

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

Структура:

Python dict — это хеш-таблица с открытой адресацией.

Компоненты:

1. Хеш-функция — преобразует ключ в число
2. Массив слотов — хранит пары ключ-значение
3. Индекс — определяет позицию в массиве

Процесс доступа по ключу:

d = {"name": "Alice", "age": 30}
value = d["name"]

1. Вычисляется hash("name")
2. Индекс = hash % размер_таблицы
3. Проверка ключа в слоте
4. Если коллизия — линейное пробирование

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

Худший случай — когда все ключи имеют одинаковый хеш (редко).

Коллизии:

# Коллизия — разные ключи с одинаковым hash % size
# Решение: открытая адресация (линейное пробирование)

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

1. Хешируемость — должен иметь __hash__()
2. Неизменяемость — хеш не должен меняться
3. Сравнимость — должен иметь __eq__()

# OK
d = {1: "int", "str": "string", (1,2): "tuple"}

# Error
d = {[1,2]: "list"}  # TypeError: unhashable type

Оптимизации в Python 3.6+:

• Словари сохраняют порядок вставки
• Compact dict — меньше памяти
• Key-sharing — для атрибутов объектов