За счет чего достиграется уникальность значений в множестве?

Уникальность в множествах (Set): механизм и реализация

Уникальность значений в множестве в Python достигается за счёт хеширования (hash()) и сравнения равенства (==). Это двухуровневый механизм, который обеспечивает эффективность и корректность.

1. Роль хеш-функции (hash)

Каждый элемент в множестве проходит через хеш-функцию:

# Хеш одинаков для одинаковых значений
print(hash(5))          # 5
print(hash(5))          # 5
print(hash("hello"))    # -5159619437318252949
print(hash("hello"))    # -5159619437318252949

# Разные объекты могут иметь разные хеши
print(hash(1))          # 1
print(hash(1.0))        # 1 (сравниваются как равные!)
print(hash("1"))        # 8765432... (другой хеш)

# Проверка
print(1 == 1.0)         # True
print(hash(1) == hash(1.0))  # True

my_set = {1, 1.0}
print(my_set)           # {1} — дубликат удален

Множество использует хеш для быстрого поиска O(1):

# Под капотом
my_set = {"apple", "banana", "cherry"}

# При добавлении:
hash_value = hash("apple")  # Вычисляется
bucket_index = hash_value % table_size  # Определяет позицию
# Проверить есть ли уже в этом bucket'е

2. Двухуровневая проверка: Hash + Equality

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def __hash__(self):
        # Хеш основан на имени
        return hash(self.name)
    
    def __eq__(self, other):
        # Полная проверка равенства
        return self.name == other.name and self.age == other.age

p1 = Person("John", 30)
p2 = Person("John", 30)  # Тот же хеш
p3 = Person("John", 25)  # Тот же хеш, но не равны

people = {p1, p2, p3}
print(len(people))  # 2 — p1 и p2 считаются одним (по хешу и ==)

# Почему 2, а не 1?
# Шаг 1: hash(p1) == hash(p2) ✓ (оба "John")
# Шаг 2: p1 == p2 ✓ (имя и возраст совпадают)
# → p2 отклонен как дублик

# Шаг 1: hash(p1) == hash(p3) ✓ (оба "John")
# Шаг 2: p1 == p3 ✗ (возраст отличается)
# → p3 добавлен как отдельный элемент

3. Требования к __hash__ и __eq__

Связь между ними критична:

# ❌ Плохо — нарушает контракт
class BadExample:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return hash(self.value)  # Основано на value
    
    def __eq__(self, other):
        return True  # Все считаются равными!

obj1 = BadExample(1)
obj2 = BadExample(2)

bad_set = {obj1, obj2}
print(len(bad_set))  # Может быть 1 или 2 — непредсказуемо!

# ✅ Хорошо — согласованное поведение
class GoodExample:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return hash(self.value)
    
    def __eq__(self, other):
        if not isinstance(other, GoodExample):
            return False
        return self.value == other.value

obj1 = GoodExample(1)
obj2 = GoodExample(2)
obj3 = GoodExample(1)  # Дублик

good_set = {obj1, obj2, obj3}
print(len(good_set))  # 2 — предсказуемо

Правило: if a == b, then hash(a) == hash(b)

# Проверка
a = "python"
b = "python"

print(a == b)                  # True
print(hash(a) == hash(b))      # True ✓

# Нарушение приведет к ошибкам
class Broken:
    def __hash__(self):
        return 42  # Один хеш для всех
    
    def __eq__(self, other):
        return id(self) == id(other)  # Сравнение по памяти

b1 = Broken()
b2 = Broken()
print(b1 == b2)         # False (разные объекты в памяти)
print(hash(b1) == hash(b2))  # True (оба 42)
# → Множество может потерять элементы!

4. Immutability — требование для хешируемости

Объекты в множестве должны быть неизменяемы:

# ❌ Списки не хешируемы (изменяемы)
my_list = [1, 2, 3]
my_set = {my_list}  # TypeError: unhashable type: 'list'

# ✅ Кортежи хешируемы (неизменяемы)
my_tuple = (1, 2, 3)
my_set = {my_tuple}  # OK

# ❌ Словари не хешируемы
my_dict = {"key": "value"}
my_set = {my_dict}  # TypeError: unhashable type: 'dict'

# ❌ Пользовательский класс с изменяемыми полями
class Mutable:
    def __init__(self, data):
        self.data = data  # ❌ Изменяемо
    
    def __hash__(self):
        return hash(id(self))

obj = Mutable([1, 2, 3])
obj.data.append(4)  # Изменяем объект
# Теперь хеш устарел, множество работает неправильно

# ✅ Правильно — неизменяемые данные
from dataclasses import dataclass

@dataclass(frozen=True)  # Запрещает изменения
class Immutable:
    x: int
    y: int

obj = Immutable(1, 2)
immutable_set = {obj}  # OK

5. Практический пример: отслеживание уникальных пользователей

from dataclasses import dataclass
from typing import Set

@dataclass(frozen=True)
class User:
    user_id: int
    email: str
    username: str
    
    def __hash__(self):
        # Хеш только по user_id (основной идентификатор)
        return hash(self.user_id)
    
    def __eq__(self, other):
        if not isinstance(other, User):
            return False
        # Полная проверка
        return (self.user_id == other.user_id and
                self.email == other.email and
                self.username == other.username)

# Использование
users: Set[User] = set()

user1 = User(user_id=1, email="john@example.com", username="john_doe")
user2 = User(user_id=2, email="jane@example.com", username="jane_doe")
user3 = User(user_id=1, email="john@example.com", username="john_doe")  # Дублик

users.add(user1)
users.add(user2)
users.add(user3)

print(len(users))  # 2 — user3 считается дублик user1

# Быстрый поиск
if user1 in users:  # O(1) благодаря хешу
    print("User found")

6. Оптимизация: фиксирование хеша для сложных объектов

class CachedHash:
    def __init__(self, name, age):
        self.name = name
        self.age = age
        self._hash = None  # Кеш хеша
    
    def __hash__(self):
        if self._hash is None:
            # Вычислить один раз
            self._hash = hash((self.name, self.age))
        return self._hash
    
    def __eq__(self, other):
        if not isinstance(other, CachedHash):
            return False
        return self.name == other.name and self.age == other.age

obj = CachedHash("Alice", 30)
my_set = {obj, obj, obj}
print(len(my_set))  # 1

7. Внутренняя структура: Hash Table

# Упрощённое объяснение того, как работает множество
class SimpleSet:
    def __init__(self, size=16):
        self.table = [None] * size
        self.count = 0
    
    def add(self, item):
        h = hash(item)
        index = h % len(self.table)
        
        # Проверить есть ли уже
        if self.table[index] is not None:
            if item == self.table[index]:
                return  # Уже есть
        
        # Добавить
        self.table[index] = item
        self.count += 1
    
    def __contains__(self, item):
        h = hash(item)
        index = h % len(self.table)
        return self.table[index] == item

ss = SimpleSet()
ss.add(5)
ss.add(10)
ss.add(5)  # Дублик
print(5 in ss)  # True — O(1) поиск
print(ss.count)  # 2

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

• Объекты в множестве должны быть неизменяемы (frozen dataclass, namedtuple)
• __hash__ и __eq__ должны быть согласованы: если объекты равны, хеши должны быть равны
• Не изменяй объекты после добавления в множество — множество перестанет работать
• Для настраиваемых классов явно определяй __hash__ и __eq__
• Тестируй что дублики действительно считаются дублик