Какая сложность у хэш-индекса

Временная сложность основных операций для хэш-индекса (например, в Python dict или set):

• Вставка (insert): O(1) в среднем случае, O(n) в худшем (при коллизиях)
• Поиск (lookup): O(1) в среднем случае, O(n) в худшем
• Удаление (delete): O(1) в среднем случае, O(n) в худшем

Пример с Python dict:

d = {}
d['key'] = 'value'  # O(1)
val = d['key']      # O(1)
del d['key']        # O(1)

Худший случай возникает редко, так как Python автоматически увеличивает размер хэш-таблицы при заполнении. Для минимизации коллизий используется качественная хэш-функция.