Quelle est la complexité temporelle de l'opération de recherche d'un élément dans une table de hachage dans les cas moyens et pires?

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

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

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

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