Основная идея

Хэш-таблица — структура данных, в которой доступ к элементу строится по вычисленному хэшу ключа.
Цель хэширования — минимизировать количество коллизий и обеспечить быстрый поиск.

Временная сложность поиска

1. Средний случай:

   • Сложность: O(1)

   • При хорошей хэш-функции элементы распределены равномерно.

   • Количество коллизий минимально, поэтому поиск почти мгновенный.

2. Худший случай:

   • Сложность: O(n)

   • Возникает, если все ключи попали в одну корзину (например, плохая хэш-функция).

   • Тогда приходится перебрать все элементы внутри списка/цепочки.

Почему на практике почти всегда O(1)

• Используются хорошие хэш-функции.

• Таблица автоматически расширяется при заполнении (load factor).

• Коллизии распределяются равномерно.

Пример

Небольшая проверка времени поиска:

d = {i: i*2 for i in range(1000000)}
x = d[123456]  # O(1) в среднем

Вывод

Поиск в хэш-таблице обычно O(1) и только в теории может стать O(n).