On Wed, 7 Jan 1998, Patrick J. Dughi wrote:
> It's really terribly simple.
>
> Just avoid powers of two for the #'s in your hash table -
> it promotes clustering, and thats bad.
Why? I remember this mentioned in the textbook we used, but I don't
remember the explanation.
I use a power-of-two number for all my hash tables, and I have not
encountered any data for which it was that (value-of-key % hash-size)
tended to be the same number for much data, where hash-size was a power of
2.
Only example of clustering because of a bad hash key I can think of are
vnums, 100 ora multiple thereof would be a bad key to use, since most
areas start with a n*100 +1 vnum, but seldom take up to n*100 + 99.
Using a power-of-2 is actualy slightly faster than a non-power of two
since operation like x % (1 << 10) can be reduced to zeroing out all but
the last 10 bottom 10 bits.
=============================================================================
Erwin Andreasen Herlev, Denmark <erwin@pip.dknet.dk> UNIX System Programmer
<URL:http://www.abandoned.org/drylock/> <*> (not speaking for) DDE
=============================================================================
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST