Как работает множество в Python?

Как работает множество в Python

Множество (set) — это неупорядоченная коллекция уникальных элементов. Реализовано на базе хеш-таблицы, что даёт O(1) для основных операций.

1. Основы работы со множествами

# Создание
s = {1, 2, 3, 4, 5}
print(s)  # {1, 2, 3, 4, 5} (порядок не гарантирован)

# Пустое множество (не {}!)
empty_set = set()
print(empty_set)  # set()

# Из списка
s = set([1, 2, 2, 3, 3, 3])
print(s)  # {1, 2, 3} - дубликаты удалены

# Из строки
s = set('hello')
print(s)  # {'h', 'e', 'l', 'o'}

2. Внутренняя реализация (хеш-таблица)

Python использует хеш-таблицу для быстрого поиска:

Элемент → hash(элемент) → индекс в таблице → значение

Пример:
  Элемент: 42
  hash(42) = 42
  индекс = 42 % размер_таблицы
  таблица[индекс] = 42

Сложность операций:

# Все эти операции O(1) в среднем
42 in s          # Поиск
s.add(7)          # Добавление
s.remove(3)       # Удаление

Для сравнения со списком:

my_list = [1, 2, 3, 4, 5, 6, 7]
42 in my_list    # O(n) - проходит весь список!

my_set = {1, 2, 3, 4, 5, 6, 7}
42 in my_set     # O(1) - прямое обращение в таблицу

3. Условие: элементы должны быть хешируемы

Элемент можно добавить в множество только если его можно захешировать (hash()):

# ✅ Хешируемые типы (можно в set)
s = {1, 2, 3}                    # int
s = {"a", "b", "c"}              # str
s = {(1, 2), (3, 4)}             # tuple
s = {1, 2.5, "text", (1, 2)}     # смешанные типы

# ❌ НЕхешируемые типы (ошибка!)
s = {[1, 2, 3]}                  # TypeError: unhashable type: 'list'
s = {{"key": "value"}}            # TypeError: unhashable type: 'dict'

my_set = {1, 2, 3}
s = {my_set}                     # TypeError: unhashable type: 'set'

Чтобы использовать список или dict, преобразуй в кортеж:

s = {(1, 2, 3)}                  # OK - tuple хешируемый

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

Добавление и удаление

s = {1, 2, 3}

s.add(4)                        # Добавить элемент
print(s)                         # {1, 2, 3, 4}

s.add(4)                        # Нет ошибки, но не добавится
print(s)                         # {1, 2, 3, 4}

s.remove(2)                      # Удалить (ошибка если нет)
print(s)                         # {1, 3, 4}

s.remove(10)                     # KeyError!

s.discard(10)                    # Удалить без ошибки
print(s)                         # {1, 3, 4}

s.pop()                          # Удалить произвольный элемент
s.clear()                        # Очистить
print(s)                         # set()

Проверка принадлежности

s = {1, 2, 3, 4, 5}

2 in s                           # True - O(1)!
print(2 in s)                    # True

10 in s                          # False

5. Теоретико-множественные операции

Объединение (union)

s1 = {1, 2, 3}
s2 = {3, 4, 5}

s3 = s1 | s2                    # {1, 2, 3, 4, 5}
s3 = s1.union(s2)               # То же самое

Пересечение (intersection)

s1 = {1, 2, 3}
s2 = {3, 4, 5}

s3 = s1 & s2                    # {3}
s3 = s1.intersection(s2)        # То же самое

Разность (difference)

s1 = {1, 2, 3}
s2 = {3, 4, 5}

s3 = s1 - s2                    # {1, 2}
s3 = s1.difference(s2)          # То же самое

Симметричная разность

s1 = {1, 2, 3}
s2 = {3, 4, 5}

s3 = s1 ^ s2                    # {1, 2, 4, 5}
s3 = s1.symmetric_difference(s2)  # То же самое

6. Сравнение множеств

s1 = {1, 2, 3}
s2 = {1, 2, 3}
s3 = {1, 2, 3, 4}

s1 == s2                        # True (одинаковые элементы)
s1 < s3                         # True (s1 подмножество s3)
s1 <= s3                        # True (подмножество или равны)
s3 > s1                         # True (супермножество)

s1.issubset(s3)                 # True
s3.issuperset(s1)               # True
s1.isdisjoint({4, 5})           # True (нет общих элементов)

7. Frozenset (неизменяемое множество)

Для случаев, когда нужна константность:

# Обычное множество можно менять
s = {1, 2, 3}
s.add(4)  # OK

# Frozenset неизменяемый
fs = frozenset([1, 2, 3])
fs.add(4)  # AttributeError

# Зато frozenset можно использовать как ключ словаря
dict_with_set_key = {
    frozenset({1, 2}): "value1",
    frozenset({3, 4}): "value2"
}

# И как элемент множества
sets_of_sets = {
    frozenset({1, 2}),
    frozenset({3, 4}),
    frozenset({1, 2})  # Дубликат удалится
}
print(sets_of_sets)  # {frozenset({3, 4}), frozenset({1, 2})}

8. Практические примеры

Удаление дубликатов

numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
unique = list(set(numbers))
print(unique)  # [1, 2, 3, 4]

Поиск общих элементов (intersection)

list1 = [1, 2, 3, 4, 5]
list2 = [3, 4, 5, 6, 7]

common = set(list1) & set(list2)
print(common)  # {3, 4, 5}

Быстрый поиск по ID

# Слабо эффективно (список, O(n))
user_ids = [1, 2, 3, 4, 5, 100000]

def is_valid(user_id):
    return user_id in user_ids  # O(n)

# Эффективно (множество, O(1))
valid_ids = {1, 2, 3, 4, 5, 100000}

def is_valid(user_id):
    return user_id in valid_ids  # O(1)

Фильтрация по списку исключений

data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
exclude = {2, 4, 6, 8}

filtered = [x for x in data if x not in exclude]
print(filtered)  # [1, 3, 5, 7, 9]

9. Производительность

import time

# Список (O(n))
my_list = list(range(1000000))
start = time.time()
999999 in my_list
print(f"List: {(time.time() - start) * 1000:.2f}ms")  # ~40ms

# Множество (O(1))
my_set = set(range(1000000))
start = time.time()
999999 in my_set
print(f"Set: {(time.time() - start) * 1000:.2f}ms")  # ~0.001ms

Ключевые выводы

1. Множество = хеш-таблица с O(1) для поиска, добавления, удаления
2. Элементы должны быть уникальные и хешируемые
3. Порядок не гарантирован (в Python 3.7+ используется insertion order, но на это не надо полагаться)
4. Теоретико-множественные операции встроены: union, intersection, difference
5. Используй set вместо list когда нужна быстрая проверка принадлежности
6. Frozenset — для неизменяемых множеств (ключи dict, элементы set)

Множества — мощный инструмент для оптимизации кода!