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

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

Пример с Python (используется встроенный dict):

my_dict = {'a': 1, 'b': 2, 'c': 3}
# Поиск элемента - O(1) в среднем
value = my_dict.get('b', None)  # вернет 2