[lug] Hash vs list

[George Sexton]

A binary search within an array could give a pretty good result. If the
output of the hash function is not really good then a binary search would
find a record in approximately 20 comparisons.

If the hash function is poor and there are a lot of collisions then you
could end up with a lot more than 20 comparisons.

Of course a binary search only works if the data is already sorted.

George Sexton
MH Software, Inc.
http://www.mhsoftware.com/
Voice: 303 438 9585
 

> -----Original Message-----
> From: lug-bounces at lug.boulder.co.us [mailto:lug-bounces at lug.boulder.co.us]
> On Behalf Of Jeff Schroeder
> Sent: Friday, April 21, 2006 6:11 PM
> To: LUG Boulder
> Subject: [lug] Hash vs list
> 
> I'm curious whether searching for a single value in a hash is generally
> (always?) faster than searching for it in a list.  The programming I'm
> doing is in PHP, but I think it's a question with a general answer.
> 
> For example, assume I have a list of a million e-mail addresses [1] and
> I want to very quickly check whether a certain address is in that list.
> If I had a one-dimensional array, I could use the PHP function
> in_array() to determine whether I'm in the list:
> 
> $address_list = array("guy at place.com", "god at heaven.org", ...);
> if(in_array("jeff at zingstudios.net", $address_list)) ...
> 
> On the other hand, I could construct a hash with the same data:
> 
> $address_list = array("guy at place.com" => 1, "god at heaven.org" => 1, ...);
> if($address_list{"jeff at zingstudios.net"}) ...
> 
> Since hashes are designed to provide fast lookups of any given key, it
> seems to me that the second approach would yield results more
> efficiently.  But I never took a data structures class, so I may be
> missing something.
> 
> Thoughts?
> 
> Thanks,
> Jeff
> 
> [1] No, I'm not a spammer. :)  It's just an example.