Как dict и set реализованы внутри? Какова сложность получения элемента? Сколько памяти потребляет каждая структура?
dict и set в Python реализованы как хэш-таблицы со средней сложностью доступа к элементу O(1). В худшем случае при большом числе коллизий сложность операций может вырасти до O(n). Памяти они потребляют больше, чем число элементов, из‑за запасов под слоты и особенностей реализации.
dict, так и set в Python реализованы с использованием хэш-таблиц. Хэш-таблица — это структура данных, которая использует хэш-функцию для преобразования ключа в индекс в массиве слотов, содержащих указатели на элементы; в современных реализациях dict это, по сути, индекс в массиве индексов другой структуры, где уже хранятся хэши и указатели на ключи и значения. Это обеспечивает быстрый доступ к данным, поскольку время доступа к элементу по ключу в хэш-таблице в среднем составляет O(1).dict и проверки принадлежности элемента в set составляет O(1), так как доступ идёт по хэшу и индексу в массиве слотов хэш-таблицы. Поиск элемента в словаре «по значению», без знания ключа, требует перебора и в среднем имеет сложность O(n). В худшем случае для обеих структур сложность операций может достигать O(n), когда возникает большое количество коллизий хэшей (ситуаций, когда два разных входных значения дают одинаковый хеш-код при использовании хеш-функции) и приходится последовательно просматривать несколько записей.dict и set, зависит от количества элементов и количества слотов в хэш-таблице. Обычно хэш-таблицы имеют некоторую избыточность, чтобы уменьшить вероятность коллизий и улучшить производительность. Поэтому фактическое потребление памяти может быть больше, чем количество элементов. В целом, потребление памяти для dict и set растет пропорционально количеству элементов, но может быть нелинейным из-за хэш-таблицы.Отметьте свой прогресс