Карточка Middle Коллекции спрашивают часто обновлено
Как устроен dict в CPython
Вопрос
Как устроен dict в CPython в двух словах?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
Хеш-таблица с открытой адресацией. Записи (хеш, ключ, значение) лежат в компактном массиве в порядке вставки, а разреженный массив индексов указывает на них.
Ответ
Хеш-таблица с открытой адресацией. Записи (хеш, ключ, значение) лежат в компактном массиве в порядке вставки, а разреженный массив индексов указывает на них. Поиск: хеш, слот, пробы при коллизии, сравнение ключа через ==. При заполнении примерно на 2/3 таблица увеличивается.
Разбор
Компактное представление появилось в 3.6 и дало экономию памяти и порядок вставки. Среднее O(1), худшее O(n) при массовых коллизиях.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.