> Как устроено множество (set) в Python (Python)

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

Ключевые особенности:

• Элементы должны быть хешируемыми (неизменяемыми типами, например, числа, строки, кортежи). Списки или другие множества нельзя добавить.
• Порядок элементов не гарантирован (до Python 3.7 он был случайным, с 3.7 сохраняется порядок вставки как деталь реализации, но не является контрактом языка).
• Внутренне хеш-таблица динамически расширяется при заполнении (обычно при загрузке > 2/3), что может вызывать редкие рехеширования с амортизированной O(n) стоимостью.

Пример:

PYTHON
s = {1, 2, 3}
s.add(4)
print(1 in s)  # True

Для множеств также доступны операции над множествами: объединение (|), пересечение (&), разность (-) и симметрическая разность (^), которые реализованы эффективно через хеш-таблицу.