Какова сложность времени для поиска элемента в хэше Perl?

Question

Предположим, у меня есть файл с n словами.Когда я читаю каждое слово в файле, я буду хранить его в хэше (в Perl).Когда я возвращаюсь и ищу слово в хэше, какова временная сложность поиска строки (слова) в хэше?

Например:

my %seen = ();
@arr=("one","two","three");
foreach $item (@arr){
    if($seen{$item}) {//do something}
}

В этой программе я ищу элемент в хэше.Какова временная сложность поиска строки в хэше?

Кроме того, можно ли уточнить, как хэш реализован в Perl?(внутренне что-то происходит в хэше? или это просто ассоциативный массив)

Answer 1

Хеши Perl обеспечивают постоянный поиск. Они реализованы в виде настоящих хеш-таблиц (при необходимости автоматическая перенастройка), а не ассоциативных массивов.

Answer 2

Если вы хотите увидеть, как Perl реализует хэши, пройдите через источник в hv.c и hv.h . Если вам нужен только обзор, вы можете попробовать perlguts . Однако, как говорит Фридо, время поиска любой клавиши совпадает с временем поиска любой другой клавиши. Это настоящий хэш.

Возможно, вы захотите увидеть эссе Джона Бентли о хэшах в Программирование жемчужин (не книга на Perl).