[lug] Hash vs list

[Ted Logan]

On 4/21/06, Rob Nagler <nagler at bivio.biz> wrote:
> Pre-optimization is the root of all evil.  :-) Write the code the
> fastest way for you to get it written.  If everything is fine, you did
> a great job.  If it isn't, figure out what part is slow by writing a
> performance test.

Premature optimization is bad, but so is premature pessimization. If
the code in question is a small script, and you discover that there's
a major performance problem in using an array versus using a hash,
it's easy enough to rewrite... but if it's in the core of a large
application where everything depends on it, changing the core data
structure is going to be a pain, even if it's ultimately worth it.
Most times, though, it doesn't matter; computers are fast, and
programmer time is expensive.

Back to the original question, the original poster is correct that
hashes are intended to provide fast lookups within datasets, and will
probably be faster. Looking for a single value in an array involves
searching the entire array, which gets more time-consuming as the
array grows. Hash tables, however, typically provide constant-time
operation -- the time it takes to look up a specific element in a hash
table does not depend on the number of items in the hash table.

Wikipedia's hash table article gives a good overview of how hashes operate:

http://en.wikipedia.org/wiki/Hash_table

(For the record, I'm not actually certian which data structure PHP
uses to implement its associative arrays.)

--
Ted Logan
Software Engineer
ted.logan at gmail.com
http://jaeger.festing.org/