🚀 go-pugleaf

In article <jgkDFv094.JKJ@netcom.com> Joe Keane <jgk@netcom.com> writes:
>Whenever i find some important hash table, one of the changes that i make is:
>Take out that stupid `%' operator!
>
>People that don't have low-level knowledge of machines don't realize how slow
>that remainder operation is.  Of course, it depends on the machine, so it can
>range from rather slow to extremely slow.  With no exaggeration, a good hash
>table can do several lookups in the time it takes to compute one remainder.

_I_ think you're exaggerating.  I don't think you can handle a single
successful lookup (or collision) in the amount of time it takes to do
a remainder.  If we're hashing strings, there's a string compare
implied in either case, not to mention the possibility of 2 or more
cache (tlb, ...) misses along the way.

>In many applications, various hash tables are just critical to performance.
>The most important thing for a hash table like this is for it to *go fast*;

Hash tables offer constant (expected) time access.  Thus, they're
almost always helpful asymptotically.  Getting a bad distribution of
keys can provoke O(n) time per lookup, where n is the number of keys
in the table.  I'm glad to spend a little constant factor to help
avoid that possibility.

On the other hand, for small data sets, where the possibility of
asymptotic explosion doesn't matter, then you can do as you please.

Preston Briggs