Что общего между словарем и множеством (set) в Python

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

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

Как отвечать

Общего у них больше, чем различий:

• обе построены на хеш-таблице: элемент кладётся по значению hash(), а не по порядку сравнения;
• требование к элементам одинаковое: ключ словаря и элемент множества должны быть хешируемыми, то есть неизменяемыми. int, str, tuple из хешируемых подходят, list и dict нет, вместо вложенного set берут frozenset;
• уникальность: повторный ключ перезаписывает значение, повторный элемент множества просто игнорируется;
• средняя сложность проверки вхождения, вставки и удаления O(1), в худшем случае при массовых коллизиях O(n);
• проверка пишется одинаково, key in d и x in s, причём у словаря это проверка по ключам, а не по значениям;
• множество это по сути словарь без значений, поэтому d.keys() ведёт себя как множество и поддерживает операции &, |, -.

Различия стоит назвать сразу: словарь хранит пары и с версии 3.7 гарантирует порядок вставки, множество порядок не хранит вообще. Пустой литерал {} это словарь, пустое множество только set().

d = {"a": 1, "b": 2}
s = {"b", "c"}
d.keys() & s   # {'b'}

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

Говорят «обе структуры неупорядоченные». Для множества это верно, а словарь с версии 3.7 сохраняет порядок вставки, и это гарантия языка, а не деталь реализации.

Второе: подают O(1) как обещание. Это средняя амортизированная оценка. Свой класс с плохим __hash__, например возвращающим константу, превращает таблицу в линейный список, и поиск становится перебором.

Третье: путают неизменяемость и хешируемость. Ошибку unhashable type замечают сразу, а по-настоящему больно, когда объект хешируемый, но его меняют уже после вставки: хеш перестаёт совпадать с корзиной, и элемент теряется внутри контейнера, хотя физически там лежит.