Как в set достигается уникальность элементов?

Как в set достигается уникальность элементов

В Python set достигает уникальности элементов через комбинацию хеширования (hashing) и проверки равенства (equality). Это сложная, но эффективная система на основе хеш-таблиц.

Хеш-функция

Каждый объект в Python имеет встроенную хеш-функцию __hash__(), которая преобразует объект в целое число:

print(hash(42))              # 42
print(hash('hello'))         # -1234567890123456789 (зависит от реализации)
print(hash((1, 2, 3)))       # некоторое целое число

try:
    hash([1, 2, 3])          # TypeError: unhashable type: 'list'
except TypeError as e:
    print(e)

Важно: листы и словари не имеют __hash__(), поэтому их нельзя добавить в set.

Индексирование в set

Внутренне set использует хеш-таблицу. Когда вы добавляете элемент:

1. Вычисляется хеш элемента
2. Вычисляется индекс в массиве: index = hash(element) % table_size
3. Проверяется коллизия: если на этом индексе уже что-то есть, сравнивают элементы через ==
4. Добавляется или игнорируется элемент

s = {1, 2, 3}
s.add(2)  # hash(2) % table_size → уже есть 2, поэтому не добавляется
s.add(4)  # hash(4) % table_size → новое место, добавляется
print(s)  # {1, 2, 3, 4}

Двойное условие: hash + equality

Для уникальности нужно одновременно соблюдение двух условий:

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):
        if not isinstance(other, Person):
            return False
        return self.name == other.name and self.age == other.age

p1 = Person('Alice', 30)
p2 = Person('Alice', 30)
p3 = Person('Bob', 25)

s = {p1, p2, p3}
print(len(s))  # 2, потому что p1 и p2 имеют одинаковый хеш и равны
print(p1 == p2)  # True
print(p1 is p2)  # False (разные объекты)

Важное правило: консистентность hash и equality

Правило: если a == b, то hash(a) == hash(b).

Если нарушить это правило, set будет работать неправильно:

class BadExample:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 1  # Всегда одинаковый хеш
    
    def __eq__(self, other):
        return isinstance(other, BadExample) and self.value == other.value

b1 = BadExample(1)
b2 = BadExample(1)
b3 = BadExample(2)

s = {b1, b2, b3}
print(len(s))  # Должно быть 2, но может быть неправильно

# Правильно: если hash() одинаковый, Python проверит через ==

Разница между hash и equals

class Example:
    def __init__(self, x):
        self.x = x
    
    def __hash__(self):
        return self.x // 10  # Хеши совпадают для 10-19, 20-29 и т.д.
    
    def __eq__(self, other):
        return isinstance(other, Example) and self.x == other.x

e1 = Example(10)
e2 = Example(11)
e3 = Example(10)

s = {e1, e2, e3}
print(len(s))  # 2, потому что e1 == e3 несмотря на e1 is e3 = False

for elem in s:
    print(elem.x)  # Выведет 10 и 11

Хеш-коллизии и разрешение

В Python коллизии разрешаются методом открытой адресации (open addressing):

# Упрощённый пример логики внутри set
class SimpleHashTable:
    def __init__(self, size=8):
        self.table = [None] * size
    
    def add(self, item):
        index = hash(item) % len(self.table)
        
        # Если место занято
        if self.table[index] is not None:
            if self.table[index] == item:
                return  # Элемент уже есть
            # Иначе находим следующее свободное место (linear probing)
            i = 1
            while self.table[(index + i) % len(self.table)] is not None:
                if self.table[(index + i) % len(self.table)] == item:
                    return
                i += 1
            index = (index + i) % len(self.table)
        
        self.table[index] = item

ht = SimpleHashTable()
ht.add(1)
ht.add(2)
ht.add(1)  # Игнорируется
print([x for x in ht.table if x is not None])  # [1, 2]

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

Временная сложность:

• Добавление: O(1) в среднем, O(n) в худшем (много коллизий)
• Поиск: O(1) в среднем
• Удаление: O(1) в среднем

Python автоматически увеличивает размер таблицы при заполнении более чем на 2/3 для минимизации коллизий.

Практические выводы

• Элементы set должны быть hashable (иметь __hash__() и __eq__())
• Если переопределяешь __eq__(), должен переопределить и __hash__()
• Неизменяемые объекты (int, str, tuple) - hashable по умолчанию
• Изменяемые объекты (list, dict, set) - не hashable
• Хеш не должен изменяться во время жизни объекта (не менять атрибуты)

Этот механизм делает set одной из самых эффективных структур данных для проверки принадлежности элемента.