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

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