Какая сложность операции поиска значения в Set в Python?

Сложность операции поиска в Set

Операция поиска значения в Set имеет O(1) сложность в среднем случае.

Как это работает

Python использует хеш-таблицу как базовую структуру данных для Set. Когда вы проверяете наличие элемента, Python:

1. Вычисляет хеш элемента с помощью встроенной функции hash()
2. Использует этот хеш для прямого доступа к позиции в хеш-таблице
3. Сравнивает искомый элемент с элементом на этой позиции

my_set = {1, 2, 3, 4, 5, 100, 1000}

# O(1) операция
if 100 in my_set:  # Очень быстро, независимо от размера set
    print("Найдено")

# Для сравнения - список
my_list = [1, 2, 3, 4, 5, 100, 1000]
if 100 in my_list:  # O(n) в худшем случае
    print("Найдено")

Худший случай: O(n)

В редких ситуациях поиск может деградировать до O(n):

• Коллизии хешей — когда разные элементы имеют одинаковый хеш, Python должен пройти по цепочке коллизий
• Плохая хеш-функция — если хеш-функция распределяет значения неравномерно

# Пример искусственного создания коллизий (редко встречается в реальности)
class BadHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 0  # Все объекты имеют одинаковый хеш
    
    def __eq__(self, other):
        return isinstance(other, BadHash) and self.value == other.value

bad_set = {BadHash(i) for i in range(10)}
# Поиск в этом set будет O(n) из-за коллизий

Другие операции Set

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

import time

# Set O(1)
my_set = set(range(1000000))
start = time.time()
for _ in range(100000):
    999999 in my_set
set_time = time.time() - start

# List O(n)
my_list = list(range(1000000))
start = time.time()
for _ in range(100000):
    999999 in my_list
list_time = time.time() - start

print(f"Set: {set_time:.4f}s")
print(f"List: {list_time:.4f}s")
print(f"Разница: {list_time/set_time:.0f}x")

Обычно Set быстрее в сотни раз благодаря O(1) сложности.

Выводы

• Поиск в Set — O(1) в среднем случае
• Это делает Set идеальным выбором для проверки наличия элементов
• List всегда даёт O(n) для поиска
• Используйте Set когда нужна частая проверка наличия элемента