Какие элементы хранения используются в set?

Элементы хранения в set (множество)

Set в Python — это неупорядоченное хранилище уникальных элементов. Давайте разберемся, как они хранятся и как они организованы в памяти.

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

Set использует hash table для хранения элементов.

# Set хранит только уникальные элементы
my_set = {1, 2, 3, 2, 1}
print(my_set)  # {1, 2, 3}
print(len(my_set))  # 3

# Set неупорядочен (порядок не гарантирован)
my_set = {3, 1, 2}
print(my_set)  # может вывести {1, 2, 3} или {3, 1, 2}

# Только hashable объекты
my_set = {1, "hello", (1, 2)}
print(my_set)  # {1, "hello", (1, 2)}

# Не может содержать unhashable объекты
# my_set = {1, [2, 3]}  # TypeError: unhashable type: "list"

2. Hash Table структура

Set использует hash table (hash table реализация) как внутреннюю структуру.

# Внутренняя структура set (упрощённо)
class HashSet:
    def __init__(self, size=8):
        self.table = [None] * size
        self.size = 0
    
    def add(self, item):
        hash_value = hash(item)
        index = hash_value % len(self.table)
        
        # Проверка на collision (hash collision)
        while self.table[index] is not None:
            if self.table[index] == item:
                return  # Элемент уже существует
            # Linear probing для разрешения коллизий
            index = (index + 1) % len(self.table)
        
        self.table[index] = item
        self.size += 1
    
    def contains(self, item):
        hash_value = hash(item)
        index = hash_value % len(self.table)
        
        while self.table[index] is not None:
            if self.table[index] == item:
                return True
            index = (index + 1) % len(self.table)
        
        return False

# Использование
my_set = HashSet()
my_set.add(1)
my_set.add(2)
my_set.add(3)
print(my_set.contains(2))  # True

3. Hash функция и коллизии

Hash функция преобразует объект в целое число.

# Встроенная функция hash()
print(hash(42))  # 42
print(hash("hello"))  # -1234567890 (примерно)
print(hash((1, 2)))  # 3713081631934410656 (примерно)

# Hash коллизии (collision)
print(hash(1) % 10)
print(hash(11) % 10)  # Может быть то же число

# Python использует open addressing с linear/quadratic probing
# для разрешения коллизий

# Custom hash для своих объектов
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def __hash__(self):
        return hash((self.name, self.age))
    
    def __eq__(self, other):
        return self.name == other.name and self.age == other.age

people_set = {Person("Alice", 30), Person("Bob", 25)}
print(len(people_set))  # 2

4. Memory layout

Внутренняя структура в памяти.

import sys

# Размер set в памяти
empty_set = set()
print(sys.getsizeof(empty_set))  # ~216 bytes (Python 3.10)

small_set = {1, 2, 3}
print(sys.getsizeof(small_set))  # ~216 bytes (ещё мало элементов)

large_set = set(range(1000))
print(sys.getsizeof(large_set))  # ~32976 bytes (растёт при добавлении)

# Set увеличивает размер таблицы при росте
# Когда load factor > 2/3, таблица увеличивается в 4 раза

# Элементы хранятся в массиве, а не в связном списке
# Это даёт быстрый доступ O(1) в среднем случае

5. Операции с set

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

# Добавление: O(1) в среднем случае
my_set = set()
my_set.add(1)  # O(1)
my_set.add(2)
my_set.add(3)

# Удаление: O(1) в среднем случае
my_set.remove(2)  # O(1)

# Проверка принадлежности: O(1) в среднем случае
if 1 in my_set:  # O(1), очень быстро
    print("Found")

# Повторение: O(n)
for item in my_set:  # O(n)
    print(item)

# Количество элементов: O(1)
len(my_set)  # O(1)

# Объединение: O(len(s1) + len(s2))
set1 = {1, 2, 3}
set2 = {3, 4, 5}
union = set1 | set2  # {1, 2, 3, 4, 5}

# Пересечение: O(min(len(s1), len(s2)))
intersection = set1 & set2  # {3}

# Разность: O(len(set1))
difference = set1 - set2  # {1, 2}

6. Сравнение производительности

import timeit

# Проверка принадлежности
list_time = timeit.timeit(
    "99 in list(range(100))",
    number=100000
)
set_time = timeit.timeit(
    "99 in set(range(100))",
    number=100000
)

print(f"List: {list_time:.4f}s")  # 0.5+ seconds
print(f"Set:  {set_time:.4f}s")   # 0.01 seconds

# Set быстрее в 50+ раз для проверки принадлежности!

7. Hashable vs Unhashable

# Hashable объекты (могут быть в set)
hashable = [
    42,
    "hello",
    (1, 2, 3),
    frozenset({1, 2, 3}),
    True,
    None,
]

my_set = set(hashable)
print(my_set)  # Работает

# Unhashable объекты (не могут быть в set)
unhashable = [
    [1, 2, 3],  # list
    {"a": 1},   # dict
    {1, 2, 3},  # set
]

for obj in unhashable:
    try:
        my_set.add(obj)
    except TypeError as e:
        print(f"Cannot add {type(obj).__name__}: {e}")

# Решение: использовать frozenset для immutable set
my_set = {frozenset({1, 2, 3}), frozenset({4, 5, 6})}
print(my_set)  # Работает

8. Set comprehension

# Создание set через comprehension
squares = {x**2 for x in range(10)}
print(squares)  # {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}

# С условием
even_squares = {x**2 for x in range(10) if x % 2 == 0}
print(even_squares)  # {0, 4, 16, 36, 64}

# От строк
words_set = {word.lower() for word in ["Hello", "WORLD", "hello"]}
print(words_set)  # {"hello", "world"}

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

# Удаление дубликатов
data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
unique = list(set(data))
print(unique)  # [1, 2, 3, 4] (порядок может измениться)

# Сохранение порядка при удалении дубликатов
data = [1, 2, 2, 3, 3, 3]
unique = []
seen = set()
for item in data:
    if item not in seen:
        unique.append(item)
        seen.add(item)
print(unique)  # [1, 2, 3] (порядок сохранён)

# Поиск общих элементов
list1 = [1, 2, 3, 4, 5]
list2 = [4, 5, 6, 7, 8]
common = set(list1) & set(list2)
print(common)  # {4, 5}

# Поиск отличающихся элементов
different = set(list1) ^ set(list2)
print(different)  # {1, 2, 3, 6, 7, 8}

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

operations = {
    "Добавление": {
        "list": "O(1)",
        "set": "O(1)",
        "dict": "O(1)",
    },
    "Поиск": {
        "list": "O(n)",
        "set": "O(1)",
        "dict": "O(1)",
    },
    "Удаление": {
        "list": "O(n)",
        "set": "O(1)",
        "dict": "O(1)",
    },
    "Память": {
        "list": "Экономная",
        "set": "Больше",
        "dict": "Больше всех",
    },
}

Best Practices

• Используй set для проверки принадлежности — намного быстрее, чем list
• Используй set для удаления дубликатов — быстро и просто
• Помни об уникальности — все элементы должны быть уникальными
• Помни о hashability — только hashable объекты
• Set неупорядочен — не полагайся на порядок
• Используй frozenset для immutable set — когда нужна неизменяемость

Set — это мощная и быстрая структура данных для хранения уникальных элементов с быстрым поиском.