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

From: Sammy (
Date: 03/03/97

On Fri, 28 Feb 1997, Johan Eenfeldt wrote:

> If you are pretty sure that strings of same length won't have, or seldom
> will have, the same first three letters, this is an example of a simple
> hashfunction to do this (writen in mailer, take care...):

Heh.  I was planning on using some combination of the first three
characters, the last character, and the string length :)

> It is possible to optimize this quite a lot. For one thing we know that
> some ASCII values will never be used. If you end up with lots of strings,
> and many identical keyvalues, you could for example use something like
> this instead of just taking the ASCII code right of, which decrease the
> number of bits used by a char to... 5 or so.

Yep I also used 'z' - character to cut out non-alpha possibilities, since
I don't plan on supporting them in spell names.

> *Optimal* hash table sizes, or functions, only exist in theory...
> However, there are a few things to think about when choosing the size.
> As a general rule, it should be a prime number far from any power of 2.

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.

I haven't seen any explanation for the difference in methods, and I can't
give it a decent test until I have a signifigant number of spells (I have
0 at the moment).

It is nice to see a couple people actually answering questions like this


| 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