Hi, Ross.

RC>Does anybody have any information on perfect hashing functions?

RC>I gather that the general idea is to take a finite set of
RC>permissible inputs and generate a function which can efficiently
RC>map any member of the set to a unique integer in the range 0 <= n < #S,
RC>where #S is the number of members of the set of permissible inputs.

RC>Any suggestions, code or references to the literature appreciated.

Yes, that's the general idea. Selecting the general form of the hash
function is still your responsibility, but there are algorithms which
can search for solutions, given that.

For example, in lookups for words (say the reserved word list in a
programming language), you could use
    hash value := word length + associated value for first letter
                              + associated value for last letter.

An algorithm can find values to give a "minimal perfect hash function".

References - only some old ones, I'm afraid ...
  Richard J. Chichelli in Communications of the ACM, Jan 80
  Knuth volume 3
  B.A.Shiel in Comm. ACM Nov 78
  R.Sprugnoli in Comm. ACM Nov 77

There's sure to be more recent ones, but I don't know of them. I have
implemented one based on the Chichelli paper.

Regards, FIM.

 * SLMR 2.1a * Backup not found: (A)bort (R)etry (P)anic

--- Maximus 2.01wb