Какая сложность поиска в hashtable

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

Пример с dict в Python (реализован как хеш-таблица):

d = {'a': 1, 'b': 2, 'c': 3}
print(d['b'])  # O(1) в среднем

Нюансы:

• Качество хеш-функции влияет на равномерность распределения.
• При высокой нагрузке (много коллизий) требуется рехеширование.
• В Python dict автоматически масштабируется, минимизируя коллизии.