Краткий ответ

Множество обычно проверяет принадлежность быстрее благодаря хеш-таблице: хеш элемента используется для прямого поиска предполагаемой позиции, поэтому средняя сложность операции составляет O(1) против O(n) для последовательного поиска в списке. Это преимущество оплачивается дополнительной памятью, вычислением хеша и требованием хешируемости элементов.

Исторический контекст

Список хранит элементы в последовательной структуре. Чтобы найти нужный элемент без дополнительной информации, приходится сравнивать его с элементами один за другим.

Хеш-таблицы появились как способ ускорить поиск по ключу: значение хеш-функции преобразует ключ в позицию или область поиска. В Python множества используют этот подход для хранения уникальных хешируемых объектов и проверки их наличия.

Постановка проблемы

Если проверять большое число кандидатов по небольшому справочнику, список может стать узким местом: каждая проверка потенциально просматривает весь список. При тысячах или миллионах проверок это даёт суммарную сложность порядка O(n умножить на m), где n — размер списка, а m — число проверок.

Замена списка множеством не всегда бесплатна. Множество занимает больше памяти, не сохраняет порядок как часть своей основной семантики и требует, чтобы элементы были хешируемыми; изменяемые списки и словари, например, элементами множества быть не могут.

Подробное решение

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

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

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

blocked = ["bot", "crawler", "scanner"]
blocked_set = set(blocked)

for agent in incoming_agents:
    if agent in blocked_set:
        reject(agent)

В примере преобразование выполняется один раз, а повторные проверки используют множество. Если проверка выполняется всего несколько раз, стоимость создания множества и дополнительная память могут не окупиться. Кроме того, хеширование сложных объектов само по себе может быть заметным, а для маленьких коллекций линейный поиск иногда быстрее из-за меньших накладных расходов и лучшей локальности данных.

Если требуется сохранить порядок и поиск выполняется редко, список может быть подходящим выбором. Для неизменяемого набора допустим также frozenset; он хешируем сам и может использоваться, например, как ключ словаря, но по скорости принадлежности имеет тот же общий принцип, что и обычное множество.

Ситуация из практики

Сервис обрабатывает миллионы запросов и для каждого проверяет идентификатор в справочнике из нескольких десятков тысяч значений. Первоначально справочник хранился в списке, из-за чего каждая проверка могла просматривать значительную его часть.

Рассматривались три варианта. Список не требовал преобразования и сохранял порядок, но имел сложность поиска O(n). Отсортированный список с двоичным поиском давал O(log n) и меньший расход памяти, однако требовал поддерживать сортировку и отдельный алгоритм поиска. Множество обеспечивало среднюю сложность O(1) и простую проверку, но требовало больше памяти.

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

Что кандидаты часто упускают

1. Всегда ли проверка принадлежности множеству имеет сложность O(1)?

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

2. Почему нельзя поместить изменяемый список во множество?

Хеш элемента должен оставаться стабильным, пока элемент находится в таблице. Если бы содержимое списка влияло на хеш и список изменился, множество могло бы искать его уже в другой позиции и перестать находить ранее добавленный объект. Поэтому список не является хешируемым, тогда как неизменяемый tuple может быть хешируемым, если все его элементы хешируемы.

3. Когда отсортированный список может быть лучше множества?

Если коллекция велика, неизменяема, память ограничена, а требуется не только проверка принадлежности, отсортированный список может быть выгоднее. Двоичный поиск даёт O(log n), список компактнее и сохраняет порядок; кроме того, сортированная структура поддерживает операции вроде поиска диапазона. Множество обычно предпочтительнее при большом числе независимых проверок, когда важнее среднее постоянное время поиска и не требуется упорядоченность.