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

В хеш-таблице операция поиска элемента обычно имеет следующие временные характеристики:

• Средний случай: O(1) — благодаря прямому доступу по хешу, поиск выполняется за константное время при условии хорошего распределения хеш-функции и низкой загрузки таблицы.

• Худший случай: O(n) — возникает, если все элементы попали в одну корзину (коллизию), и приходится последовательно перебирать все элементы в этой корзине.

На практике благодаря хорошим хеш-функциям и механизму расширения таблицы, поиск почти всегда близок к O(1).