> Что происходит внутри dict при добавлении нового элемента (Python)

При добавлении нового элемента в словарь Python выполняет несколько шагов:

1. Вычисление хеша ключа - вызывается hash(key). Если ключ нехешируемый (например, список), возникает TypeError.

2. Определение индекса в хеш-таблице - хеш маскируется (hash & mask, где mask = size - 1), чтобы получить начальный индекс в массиве записей (entries).

3. Поиск свободной ячейки - если ячейка занята, происходит разрешение коллизий методом открытой адресации (обычно используется псевдослучайное пробирование на основе старших битов хеша). Сравнение ключей идёт по равенству (==), а не по идентичности.

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

5. Вставка новой записи - если ключ новый, запись (хеш, ключ, значение) помещается в массив entries. Также обновляется массив индексов (indices), который указывает на позицию в entries.

6. Проверка загрузки - если количество занятых ячеек превышает порог (обычно 2/3 от размера таблицы), происходит ресайз: размер таблицы увеличивается примерно вдвое, все записи перехешируются и перераспределяются.

Таким образом, амортизированная сложность вставки - O(1) в среднем, но в худшем случае (много коллизий) может деградировать до O(n).