Re: [ADVANCED] Hash-table questions [long]

From: Jörgen (
Date: 03/03/97

> THis is what I really want to understand.  I can write all the code just
> fine, and I can use primes for hash keys, but what I want to know is:
> why? I've seen one other person recommemd a prime far from 2^n, but I've
> seen many more people recommend using a prime 2^n plus or minus 1, as in
> 7, 17, 31, etc.

The general rule depends on what you are hashing. I'm not an expert in this
area (I will be after the Database Technique course :), but a friend of mine
said that it all depends on what you are hashing. Some hashingmethods gives
a bad distribution on the haskeys. Some don't. And of course, it all depends on
what you are hashing. For a mud tho, I think a number (prime) far from a power
of 2 is sufficient (unless you are converting your mud to a complete 
databasesystem :). I don't know the reason why the number should be a prime far
from a 2^n number. And I guess I won't find out either. (The one's who come up
with these ideas are like very abstract persons.. What they say, one will have
to trust.)

If you are looking for a very efficient hashing-algorithm there is one from the
BSD-dudes. (It has an excellent distribution on when it comes to strings).
I don't know where it is, but you can always do a search on the net for it. If
you're not so interested in efficiency, just implement something simple. (Just
deal with the hashkey-'collisions' and you're fine.)

// Jorgen aka Zigg
| Ensure that you have read the CircleMUD Mailing List FAQ: |
|   |
|    Or send 'info circle' to     |

This archive was generated by hypermail 2b30 : 12/18/00 PST