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

From: Daniel Koepke (dkoepke@california.com)
Date: 02/28/97


On Fri, 28 Feb 1997, Johan Eenfeldt wrote:

> The goal is for the function to map the strings as evenly as possible to
> numbers, minimizing the chanse that different strings map to same value.

Hence the use of prime numbers as the hash table's size...

> *Optimal* hash table sizes, or functions, only exist in theory...
> However, there are a few things to think about when choosing the size.

Optimal is different from perfect, although perfect hash functions
do exist, but are usually impossible to create. A perfect hash function
can be easily seen with one that hashes by date. Just take the day of
the year subtracted by one (eg., January 1 == 0, February 1 == 31).
No two will generate the same hash key and thus you have a perfect
hash function. Of course, perfect hash functions cannot exist except
by pure chance (and it's a very, very, very slim chance) when you don't
know what data you will be handling. Thus you seek the best case.

> Hardly.

I had already answered it and discussed it with Sammy via e-mail,
though.


--
Daniel Koepke
dkoepke@california.com
Forgive me father, for I am sin.


+-----------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
|   http://cspo.queensu.ca/~fletcher/Circle/list_faq.html   |
|    Or send 'info circle' to majordomo@cspo.queensu.ca     |
+-----------------------------------------------------------+



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