Как устроены структуры данных list, dict и set в Python?

Что проверяют

Знаете ли вы реализацию каждой и понимаете ли требование хешируемости.

Как отвечать

list это динамический массив указателей на объекты. Доступ по индексу за постоянное время, добавление в конец амортизированно постоянное, вставка и удаление в начале линейные, поиск по значению линейный. Порядок задаётся вами, дубликаты допустимы, элементы могут быть любыми.

dict это хеш-таблица. Доступ, вставка и удаление в среднем за постоянное время. Две особенности реализации стоит назвать:

• начиная с версии 3.7 сохранение порядка вставки это гарантия языка, а не деталь реализации. Достигается компактным устройством: отдельно плотный массив записей в порядке добавления, отдельно разреженный массив индексов;
• для атрибутов объектов используется разделяемое представление ключей, поэтому тысяча экземпляров одного класса не хранит тысячу копий имён полей.

set это та же хеш-таблица, но без значений. Даёт проверку вхождения за постоянное время в среднем и операции над множествами: объединение, пересечение, разность.

Общее требование для dict и set: ключи и элементы должны быть хешируемыми, то есть неизменяемыми по хешу. Список положить нельзя, кортеж можно, но только если внутри нет изменяемых объектов. Изменение объекта после помещения в множество ломает поиск: он остаётся в старой ячейке и больше не находится.

Про память: хеш-таблицы держат запас пустых ячеек, чтобы коллизий было мало, поэтому расходуют заметно больше, чем список с тем же числом элементов. Это осознанный размен памяти на скорость.

Выбор по операции: нужен порядок и индексы, значит список; нужен доступ по ключу, значит словарь; нужна уникальность и быстрая проверка вхождения, значит множество.

Где спотыкаются

Ищут вхождение в списке там, где нужно множество.

Пытаются использовать список как ключ словаря.

Считают сохранение порядка в словаре деталью реализации, а не гарантией.

Меняют объект после добавления в множество.