Re: data structure for strings

Karl Heinz Buchegger wrote:
> I think the comment was ment to be read as:
> There are no "general purpose perfect hash functions".
> For every problem you have to look at your expected data
> and derive a hash function for it.

"Perfect hash functions" can be made if data is known. One web resource is:

  http://www.burtleburtle.net/bob/hash/perfect.html

The basic theory reference is

  Michael L. Fredman, János Komlós, and Endre Szemerédi.   Storing a sparse table with O(1) worst case access time   J. Assoc. Comput. Mach., 31(3):538 544, 1984.

Interestingly, even if the expected data is unknown, one can perform very well (in theory and practice) by choosing a random hash function from a "universal" family of hash functions. Up to a constant factor, this is expected to be as fast as any hash function specifically designed with the expected data in mind. See:

  J. Lawrence Carter and Mark N. Wegman.   Universal classes of hash functions.
  J. Comput. System Sci., 18(2):143 154, 1979.

/Rasmus

-- 
_________________________________________________________________

 Rasmus Pagh (pagh_at_daimi.au.dk)    http://www.daimi.au.dk/~pagh/
_________________________________________________________________