Что происходит при добавлении элемента в словарь?

Процесс добавления элемента в словарь Python

При добавлении элемента в словарь происходит сложный процесс на уровне внутреннего представления, который включает хеширование, резолюцию коллизий и потенциальное переиндексирование.

Шаги добавления элемента

1. Вычисление хеша ключа

Когда вы выполняете dict[key] = value, Python сначала вычисляет хеш ключа:

d = {}
d["hello"] = 42
# Вызывается hash("hello"), что возвращает числовой хеш

2. Определение позиции в таблице хеширования

Хеш используется для вычисления индекса в внутреннем массиве словаря:

index = hash(key) & (size - 1)  # Побитовое И с маской

Маска вычисляется как size - 1, где size — размер таблицы (всегда степень 2).

3. Проверка на коллизию

Если позиция занята другим ключом, Python использует открытую адресацию для поиска свободной ячейки:

# Упрощённо:
index = hash(key) & (size - 1)
while dict[index] is not empty:
    index = (index * 5 + 1 + perturbation) & (size - 1)

4. Вставка или обновление

• Если ключ новый — в найденную позицию записывается пара (ключ, значение)
• Если ключ уже существует — значение обновляется на месте

d = {"a": 1}
d["a"] = 2  # Обновление существующего ключа
d["b"] = 3  # Добавление нового ключа

5. Проверка на переполнение и переиндексирование

В Python 3.6+ словари сохраняют порядок вставки. Когда количество элементов достигает определённого порога (примерно 2/3 размера таблицы), происходит переиндексирование (rehash):

# Внутренний процесс:
# 1. Выделяется новый, больший массив (обычно в 4 раза)
# 2. Все существующие пары перехешируются в новый массив
# 3. Старый массив освобождается

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

С Python 3.6 словари используют компактное представление:

# Вместо одного массива, используются:
# - Компактный массив (индексы ключ-значение по порядку вставки)
# - Таблица хеширования (хеш -> индекс в компактном массиве)

Это даёт два преимущества:

• Сохранение порядка вставки
• Экономия памяти

Временная сложность

• Средний случай (average): O(1) — прямой доступ
• Худший случай (worst-case): O(n) — если много коллизий (редко, вероятность мизерна)
• После переиндексирования: O(n) за одну операцию, но амортизированное O(1) для последовательности операций

Пример работы:

d = {}
print(len(d))  # 0

d["key1"] = "value1"
# hash("key1") -> индекс -> вставка в таблицу

d["key2"] = "value2"
# hash("key2") -> возможная коллизия -> открытая адресация -> вставка

if len(d) > threshold:
    # Переиндексирование
    pass

print(d)  # {"key1": "value1", "key2": "value2"}
print(list(d.keys()))  # Порядок сохранён!

Принципы оптимизации

Для быстрого добавления в словари важно:

• Использовать хешируемые типы как ключи (str, int, tuple)
• Избегать изменяемых типов (list, dict, set) как ключей
• Помнить о коллизиях при расчёте производительности

Вывод: добавление элемента в словарь — это хеширование ключа, поиск позиции в таблице с разрешением коллизий, и потенциальное переиндексирование структуры при достижении порога заполнения.