В чем разница между списками и множествами и почему множество быстрее при проверке вхождения

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

Знаете ли вы, как устроены list и set в CPython, а не только то, что «множество быстрее». Почти всегда следом спрашивают, какие объекты можно положить в множество и почему.

Как отвечать

Список это динамический массив ссылок. Он хранит порядок и дубликаты, даёт доступ по индексу за O(1), но x in lst проходит элементы по очереди и сравнивает каждый через ==, то есть O(n).

Множество это хеш-таблица. Проверка x in s устроена так:

• хеш: вычисляется hash(x), по нему находится слот в таблице;
• сравнение: если в слоте что-то лежит, сначала сравниваются хеши, и только при совпадении вызывается ==;
• коллизии: при занятом слоте CPython пробует следующие по своей схеме зондирования, пока не найдёт элемент или пустое место.

В среднем это O(1) независимо от размера, в худшем случае (много коллизий) O(n). Таблица держится разреженной и расширяется при заполнении, поэтому множество заметно тяжелее списка по памяти.

Отсюда требование: элементы должны быть хешируемыми. int, str, tuple из хешируемых, frozenset подходят, list и dict дают TypeError: unhashable type. Для своих классов __hash__ и __eq__ обязаны быть согласованы: равные объекты имеют равный хеш.

Покажите и практическую сторону. Если нужно много раз проверять вхождение, один раз постройте set за O(n) и дальше проверяйте быстро. Для одной проверки конвертация дороже прямого поиска в списке. Если нужны порядок и уникальность одновременно, подходит dict.fromkeys(lst): словари сохраняют порядок вставки с Python 3.7. Бонусом множества дают |, &, - для объединения, пересечения и разности.

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

Говорят, что O(1) это гарантия. Это среднее время, а для маленьких коллекций из пяти элементов разницу с list вы не измерите.

Считают, что множество хранит порядок, раз его хранит dict. Не хранит, а порядок обхода множества строк может меняться между запусками из-за рандомизации хешей строк.

Меняют объект после того, как положили его в множество, если его хеш зависит от изменяемых полей. Элемент остаётся в старом слоте, и in перестаёт его находить.