Да, это O (1) или постоянное время.
Мы говорим, что поиск порядка 1, или, в математической записи, O(1). Это означает, что в худшем случае поиск занимает константу время * независимо от данных.
Это амортизированное время наихудшего случая - вы можете посмотреть это, но в основном это означает, что при распределении по жизни вашего хеш-таблицы стоимость постоянна. Фактическое время наихудшего случая может отличаться от приведенного здесь, в зависимости от того, как вы создаете сегменты в хеш-таблице - оно может фактически быть в любом месте от O(1) до O(n), но теоретическое лучшее * O(1) как Я тут написал.
Еще одно замечание: я на самом деле немного неряшлив с самой нотацией: чтобы действительно сделать это правильно требуется установить нотацию .