Какая алгоритмическая сложность поиска элемента в хеш-таблице?

Какая алгоритмическая сложность поиска элемента в хеш-таблице?

Это один из самых важных вопросов на собеседованиях. Ответ: O(1) в среднем случае, O(n) в худшем. Давайте разберёмся, почему.

Средний случай: O(1)

В идеальной ситуации поиск занимает константное время:

d = {"key": "value", "hello": "world"}

# Поиск работает так:
# 1. Вычисляем hash("key") -> число
# 2. Преобразуем в индекс: hash % table_size -> индекс 5
# 3. Идём в ячейку 5 и берём значение
# Время: 3 операции, независимо от размера словаря!

value = d["key"]  # O(1)

Размер словаря не имеет значения — поиск всегда один и тот же набор операций.

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

Сценарий 1: Все коллизии

Если функция хеша плохая и все ключи дают одинаковый хеш:

# Плохая функция хеша (не используй в реальности!)
def bad_hash(key):
    return 0  # Все ключи имеют одинаковый хеш!

# При открытой адресации Python будет искать:
# Индекс 0, потом 0+1^2=1, потом 0+2^2=4, потом 0+3^2=9...
# В худшем случае проверит ВСЕ n ячеек -> O(n)

Сценарий 2: Коэффициент заполнения слишком высокий

# Словарь с 10000 элементов, но в таблице 10 ячеек
# Много коллизий, много квадратичного поиска -> O(n)

Как Python защищается от худшего случая?

1. Динамическое расширение таблицы

Когда коэффициент заполнения превышает порог, таблица расширяется:

import sys

d = {}
for i in range(100):
    d[i] = i
    # Python автоматически расширяет внутреннюю таблицу
    # при коэффициенте заполнения ~66%
    # Это поддерживает O(1) в среднем

2. Хорошая функция хеша

Встроенная функция hash() качественно распределяет значения:

# Хеши равномерно распределены
for i in range(100):
    h = hash(f"key_{i}")
    print(f"{i}: {h % 16}")  # Индексы в диапазоне 0-15
    # Результат: примерно равномерное распределение

3. Рандомизированное хеширование (Python 3.3+)

Протекция от DoS атак:

# Запуск 1
python -c "print(hash('test'))"
# 3644734281328479100

# Запуск 2
python -c "print(hash('test'))"
# -8389325883425701435

# Разные результаты, невозможно специально создать коллизии

Практическая сложность в реальном коде

Поиск в словаре

d = {i: i**2 for i in range(1000000)}

# Поиск существующего ключа: O(1) ~0.0001 мс
start = time.time()
for _ in range(100000):
    _ = d[500000]
print(f"Время: {(time.time() - start)*1000:.3f} мс")  # ~10 мс для 100k поисков

# Поиск несуществующего: O(1) ~0.0001 мс
for _ in range(100000):
    _ = d.get(999999999, None)  # Быстро понимает, что нет

Сравнение со списком

import timeit

lst = list(range(1000000))
d = {i: i for i in range(1000000)}

# Поиск в списке: O(n)
time_list = timeit.timeit(
    "999999 in lst",
    setup="lst = list(range(1000000))",
    number=10000
)  # ~5000 мс (медленно!)

# Поиск в словаре: O(1)
time_dict = timeit.timeit(
    "999999 in d",
    setup="d = {i: i for i in range(1000000)}",
    number=10000
)  # ~1 мс (быстро!)

print(f"Список медленнее в {time_list / time_dict:.0f} раз")
# Результат: Словарь быстрее в ~5000 раз!

Когда худший случай становится реальностью?

# 1. Плохая функция хеша (редко с встроенным hash())

# 2. Очень старые Python версии без рандомизации

# 3. Кастомная функция __hash__ в классе
class BadClass:
    def __init__(self, x):
        self.x = x
    
    def __hash__(self):
        return 1  # Все объекты имеют одинаковый хеш!
    
    def __eq__(self, other):
        return self.x == other.x

# Использование
objects = [BadClass(i) for i in range(1000)]
d = {obj: i for i, obj in enumerate(objects)}  # Коллизии везде!
value = d[objects[500]]  # O(n) вместо O(1)

Таблица сложностей операций со словарём

Операция          Средний  Худший   Примечание
========================================================
Поиск (get)       O(1)     O(n)     Коллизии
Добавление (set)  O(1)     O(n)     С расширением таблицы амортизировано O(1)
Удаление (del)    O(1)     O(n)     
Проверка (in)     O(1)     O(n)     
Получение всех    O(n)     O(n)     keys(), values(), items()

Интервью совет

На собеседовании скажи:

"Поиск в хеш-таблице имеет O(1) в среднем случае, потому что:

1. Мы вычисляем хеш за O(1)
2. Преобразуем в индекс за O(1)
3. Идём в ячейку и берём значение за O(1)

В худшем случае это O(n), если все ключи создают коллизии и находятся в цепочке или через открытую адресацию. Но Python защищается от этого через:

• Хорошую функцию хеша
• Рандомизированное хеширование
• Динамическое расширение таблицы

На практике словарь остаётся O(1) почти всегда."

Это покажет, что ты понимаешь не только формулу, но и реальную механику.