What is the time complexity for looking up an item in a Perl hash?

Question

Suppose I have a file with n words. As I read each word in the file, I will store it in hash (in Perl). When I go back and look up for the word in the hash, what is the time complexity of looking up a string(word) in a hash?

For example:

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

In this program, I am looking up for an item in the hash. What is time complexity of looking up for a string in a hash?

Also, could any elaborate on how hash is implemented in Perl? (internally something happens in hash? or is it just an associative array)

Answer 1

Perl hashes provide constant-time lookups. They are implemented as true hash tables (with automatic retuning as necessary), not associative arrays.

Answer 2

If you want to see how Perl implements hashes, work your way through the source in hv.c and hv.h. If you want just the overview, you might try perlguts. However, as friedo says, the time to look up any key is the same time to look up any other key. It's a real hash.

You might also want to see Jon Bentley's essays on hashes in Programming Pearls (not a Perl book).