Как происходит создание словаря?

Question

[zlodiak]

Оценить максимальную асимптотическую сложность при создании словаря(dict) можно по такой формуле:
O(len(...))

Объясните пожалуйста как создаётся словарь. Я правильно понимаю, что создание
a = dict({'q': 10, 'w': 20, 'e': 30})
происходит в 3 этапа?:

• 1. сначала создаётся словарь a = {'q': 10}
  
• 2. затем создаётся a = {'q': 10, 'w': 20}
  
• 3. затем {'q': 10, 'w': 20, 'e': 30}
  

Неужели python не может создать подобный словарь одной операцией? Возможно простыми словами объяснить что этому мешает?

Answer 1

[Roman K]

Нет.

1. Создаётся в Си структура словаря
2. Создаётся хэш-таблица на 8 элементов (это до 6 ключ-значений словаря)
3. Поочерёдно добавляются (на уровне Си) элементы

Когда ты вставляешь 7-ой элемент в словарь, хэш-таблица увеличивается в 2 раза — до 16 ячеек (это до 11 ключ-значений), все существующие в старой хэш-таблице элементы (кроме удалённых [да, удаление значения из словаря не удаляет его на самом деле до следующей реаллокации]) переезжают по одному в новую, при этом заново вычисляются хэши всех этих элементов (потому что старые хэши работали только со старым размером хэш-таблицы).

И так до бесконечности. Как только количество элементов в словаре превышает load factor хэш-таблицы (который равен 2/3) — происходит создание новой хэш-таблицы. Но не раньше.

Вот этот код, возможно, поможет тебе понять, как это работает:

import sys

def fs(s):
    if s >= 2 ** 20:
        return f"{s/(2**20):.2f}МБ"
    if s >= 2 ** 10:
        return f"{s/(2**10):.2f}КБ"
    return f"{s}Б"

def g():
    n = int((2**16) * (2/3))
    d = dict.fromkeys(range(n))
    print("Размер словаря:", fs(sys.getsizeof(d)), "Элементов:", len(d))
    for i in range(n):
        del d[i]
    print("Размер словаря всё ещё", fs(sys.getsizeof(d)), "хотя он пуст. Элементов:", len(d))
    
    # В уже пустой словарь весом 1.25мб вставляем всего лишь один элемент
    d["hello"] = "world"
    newsize = sys.getsizeof(d)
    print("Хэш-таблица превысила load factor (2/3), реаллокация. Новый размер:", fs(newsize), "Элементов:", len(d))

g()

Answer 2

[Сергей Горностаев]

Понимаете вы неправильно. Как устроен словарь можно прочитать в статье на Хабре - Немного внутренностей словарей в CPython.