Hashing is a bucket algorithm. The idea is that you look at the key, produce a number, then drop that name/value into a bucket based on that number. To check if a particular key is in the hash all you need to do is look at the key, find that number, and look in the right bucket. Assuming that there are enough buckets (Perl adjusts this dynamically) and the hashing function does a good job of distributing things (Perl has a very carefully designed hashing function) that bucket will have very few things in it and therefore will be very fast to search.
In fact Perl does a pretty good job of keeping that down to 0-3 elements per bucket.
So no matter how large your dataset (ok, within the bounds of physical memory limits) accessing a hash is basically constant time. It is slower than accessing an array, but not all that much slower.
So comparing building a hash to a linear search is actually pretty fair. If you expect to need to find things more than a (pretty small) fixed number of times, the hash should be faster. For just one it is slower. If the number is dynamic then the hash definitely makes sense.
(Yeah, I know. I am ignoring all sorts of things in that broad claim. But Perl is largely designed around the assumption that a hash lookup is constant-time and fast. In the real world that works out pretty well.)
In reply to RE (tilly) 2: Doesn't anyone do their homework anymore?
by tilly
in thread better way to find list members?
by jptxs
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |