@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 не может создать подобный словарь одной операцией? Возможно простыми словами объяснить что этому мешает?
  • Вопрос задан
  • 99 просмотров
Решения вопроса 1
@deliro
Нет.

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()
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
sergey-gornostaev
@sergey-gornostaev Куратор тега Python
Седой и строгий
Понимаете вы неправильно. Как устроен словарь можно прочитать в статье на Хабре - Немного внутренностей словарей в CPython.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
29 мар. 2024, в 11:11
10000 руб./за проект
29 мар. 2024, в 10:00
10000 руб./за проект
29 мар. 2024, в 09:59
750 руб./в час