Как устроены сеты в Python?

Внутреннее устройство сетов в Python

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

Основные характеристики

Хеш-таблица с открытой адресацией

• Сет использует хеш-таблицу для O(1) операций поиска, добавления и удаления
• Элементы должны быть хешируемыми (immutable): int, str, tuple, frozenset
• Элемент хешируется, и его хеш определяет индекс в массиве

Структура памяти

# На самом низком уровне сет содержит массив слотов
# Каждый слот может быть:
# 1. Пустым (EMPTY)
# 2. Содержать объект
# 3. Содержать tombstone (маркер удаления)

my_set = {1, 2, 3}
# Примерно так это выглядит в памяти:
# [empty, 1, empty, 2, empty, 3, empty, empty]

Коллизии и разрешение

Open addressing (открытая адресация)

• Если вычисленный индекс уже занят, Python использует пробирующую функцию
• Ищет следующий свободный слот в таблице (perturbation approach)
• Это называется "open addressing with perturbation"

# Пример коллизии
my_set = set()
my_set.add("key1")  # hash("key1") % table_size = индекс 5
my_set.add("key2")  # hash("key2") % table_size = тоже индекс 5 (коллизия!)
                     # Найдёт следующий свободный слот, например 6

Коэффициент заполнения (Load Factor)

Динамическая реаллокация

• Когда сет заполняется на ~2/3, Python расширяет таблицу (примерно в 4 раза)
• При расширении все элементы перехешируются (rehash)
• Это гарантирует, что средний случай остаётся O(1)

my_set = set()
print(len(my_set.__sizeof__()))  # Можно посмотреть размер в памяти

# При добавлении элементов память растёт экспоненциально:
for i in range(1000):
    my_set.add(i)
# После каждого resize таблица становится больше

Сравнение с другими структурами

Сет vs Список

• Список: O(n) поиск, но сохраняет порядок (в Python 3.7+)
• Сет: O(1) поиск, уникальные элементы, неупорядочен

Сет vs Словарь

• Словарь: хеш-таблица с key-value парами
• Сет: хеш-таблица только с ключами (значения = пусто)
• Обе структуры используют одинаковый механизм хеширования

Требования к элементам

Хешируемость

# ✅ Хешируемые (immutable)
my_set = {1, "string", (1, 2), frozenset([1, 2])}

# ❌ Нехешируемые (mutable)
my_set = {[1, 2]}  # TypeError: unhashable type
my_set = {{1: 2}}  # TypeError: unhashable type

Консистентность хеша

• Элемент не должен менять хеш во время нахождения в сете
• Строки, кортежи, числа безопасны
• Пользовательские объекты должны иметь стабильный hash

class User:
    def __init__(self, name):
        self.name = name
    
    def __hash__(self):
        return hash(self.name)
    
    def __eq__(self, other):
        return self.name == other.name

users = {User("Alice"), User("Bob")}

Операции и их сложность

Особенности в Python 3.10+

Улучшения в мордернизации

• Таблица стала более компактной в памяти
• Уменьшилась фрагментация при частых изменениях
• Улучшена кеш-локальность для более быстрого доступа

# В Python 3.10+ сеты занимают меньше памяти благодаря 
# оптимизированному способу хранения индексов
import sys
my_set = {i for i in range(1000)}
print(sys.getsizeof(my_set))  # Компактнее, чем в Python 3.9

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

# Удаление дубликатов из списка за O(n)
unique_list = list(set([1, 2, 2, 3, 3, 3]))
# [1, 2, 3] (порядок не гарантирован)

# Проверка, есть ли общие элементы (O(n))
common = {1, 2, 3} & {2, 3, 4}
# {2, 3}

# Быстрая проверка принадлежности
if element in large_set:  # O(1) vs O(n) в списке
    pass

Сеты — это фундаментальная структура данных в Python для работы с уникальными элементами и быстрого поиска.