Насколько сложен поиск по ключу в хеш-таблице?

Поиск по ключу в хеш-таблице в среднем выполняется за время O(1) — то есть очень быстро, независимо от размера таблицы. Это достигается за счёт вычисления хеш-кода ключа и прямого доступа к соответствующей ячейке.

Однако в худшем случае, если много ключей попадают в одну корзину (коллизию), поиск может деградировать до O(n), где n — количество элементов в этой корзине. В современных реализациях, например в Python, при большом числе коллизий используется преобразование корзины в сбалансированное дерево, что снижает худший случай до O(log n).

Таким образом:

• Средний случай: O(1)
• Худший случай: O(n) или O(log n) в современных реализациях

Пример в Python:

my_dict = {'a': 1, 'b': 2, 'c': 3}
value = my_dict.get('b')  # Поиск по ключу 'b' за O(1)