Re: command_info binary tree

From: Erwin S. Andreasen (erwin@PIP.DKNET.DK)
Date: 01/08/98


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