Меня смущает сложность времени хеш-таблиц в целом.
Я понимаю, что вставка, поиск и т. Д. Амортизируются за время O (1) из-за изменения размера, того факта, что доступ к массиву после вычисления хеш-кода является постоянным временем, что мы всегда можем сохранить коэффициент загрузки хеш-таблицы на постоянное значение, и что хорошие хеш-коды позволяют нам иметь минимальные коллизии.
Однако мой вопрос касается времени выполнения самого hashCode ().
Насколько я понимаю, команды insert (), get () и т. Д. В первую очередь полагаются на вычисление хэш-кода, а затем, традиционно, на хранение данного элемента с индексом i = hashCode ()% buckets.length
Похоже, что это противоречит амортизированной производительности O (1) хеш-таблицы, поскольку производительность O (1), по-видимому, предполагает, что вычисление хэш-кода занимает постоянное время.
Однако, насколько я понимаю, для многих рекурсивных объектов (таких как связанный список) мы рекурсивно вычисляем хэш-код (для простоты я опускаю базовый вариант):
hashcode():
return this.item.hashCode() + 31 * this.next.hashCode()
Не означает ли это, что hashCode () имеет время выполнения O (N) и, следовательно, insert () для хеш-таблицы будет иметь время выполнения O (N)?
Если это так, то не будет ли insert () для хеш-таблиц довольно плохим для вставляемых элементов, которые имеют медленные функции hashCode ()? Даже для чего-то вроде вставки строки, не означает ли это, что insert () будет иметь значение O (N), где N - длина строки, поскольку мы вычисляем хеш-код на основе каждого символа в строке?
Я видел, что хеш-коды стали кэшироваться раньше, но кэширование происходит только для определенного экземпляра объекта, что означает, что нам нужно вставлять один и тот же экземпляр объекта несколько раз, чтобы кэширование имело эффект, который не ' Это кажется особенно полезным в практических ситуациях.
Если то, что я говорю, правильно, то означает ли это, что для некоторых последовательных данных, таких как строки, Trie будет иметь лучшую производительность, так как его insert () и get () будут O (L) худшим случаем, где L - длина вставляемого элемента / последовательности - это точка попыток?