Множество (set) в Python¶

Множество (set) — встроенный тип данных в языке программирования Python, представляющий собой неупорядоченную коллекцию уникальных хэшируемых объектов. Множества реализуют математическую модель множеств и поддерживают операции объединения, пересечения и разности. Тип set введён в Python начиная с версии 2.4, а неизменяемая разновидность frozenset — с версии 2.4/2.6. Множества активно используются для дедупликации данных, проверки принадлежности элементов и решения алгоритмических задач.

¶Свойства множеств

Ключевые характеристики типа set:

• Уникальность элементов — каждое значение встречается не более одного раза; повторное добавление существующего элемента не изменяет множество.
• Неупорядоченность — элементы не имеют индексов, обращение по позиции невозможно.
• Изменяемость (mutable) — можно добавлять и удалять элементы после создания.
• Хэшируемость элементов — допустимы только неизменяемые объекты: числа, строки, кортежи из хэшируемых элементов. Списки и другие множества добавить нельзя.
• Отсутствие индексации — проверка x in s выполняется в среднем за O(1) благодаря хэш-таблице.

¶Создание множеств

``python s1 = {1, 2, 3} # литерал s2 = set([1, 2, 2, 3]) # из итерируемого объекта → {1, 2, 3} s3 = set() # пустое множество s4 = {x for x in range(10) if x % 2 == 0} # множество-выражение ``

Пустое множество создаётся только через set(); запись {} создаёт словарь.

¶Основные операции

Пример:

``python a = {1, 2, 3, 4} b = {3, 4, 5, 6} a | b # {1, 2, 3, 4, 5, 6} a & b # {3, 4} a - b # {1, 2} a ^ b # {1, 2, 5, 6} ``

¶Frozenset

frozenset — неизменяемая версия множества. Используется как элемент другого множества или как ключ словаря, где требуется неизменяемость. Поддерживает те же операции сравнения и алгебраические операции, но не имеет методов add, remove и update.

``python fs = frozenset([1, 2, 3]) {fs, frozenset([4])} # множество множеств — допустимо ``

¶Внутренняя реализация

Множества в CPython реализованы на основе хэш-таблицы (той же, что и словари). Хэш-таблица обеспечивает:

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

Из-за неупорядоченности множества нельзя использовать там, где важна последовательность элементов, — в таких случаях применяют list или tuple.

¶Применение

Множества используются в типовых задачах программирования:

• Удаление дубликатов — list(set(items)) (с сохранением порядка — через dict.fromkeys).
• Быстрая проверка вхождения — замена линейного поиска по списку на O(1).
• Алгоритмы на графах — хранение множества посещённых вершин.
• Комбинаторика и математика — реализация объединений, пересечений, разностей.
• Фильтрация данных — отбор уникальных значений из потока.

¶Ограничения

• Элементы множества должны быть хэшируемыми: нельзя создать {[1, 2]} — список не хэшируем.
• Порядок элементов не определён; для упорядоченного хранения уникальных элементов используют dict.fromkeys или sorted(set(...)).
• Множества нельзя индексировать: s[0] вызовет TypeError.
• Множества-литералы {1, 2} и {} различаются: пустое множество создаётся только через set().

Источники:

• Документация Python по типам set и frozenset (docs.python.org)
• Лутц М. «Изучаем Python»
• Рамалхо М. «Python. Справочник»
• Beazley D., Jones B. K. «Python Cookbook»