[lug] Hash vs list

Jeff Schroeder jeff at zingstudios.net
Fri Apr 21 18:10:33 MDT 2006

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.



[1] No, I'm not a spammer. :)  It's just an example.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: not available
URL: <http://lists.lug.boulder.co.us/pipermail/lug/attachments/20060421/e1e11b88/attachment.pgp>

More information about the LUG mailing list