RE: [boost] Re: [Gauge for interest] Minimal perfect hash functiongenerator

From: Hartmut Kaiser (hartmutkaiser_at_[hidden])
Date: 2005-01-17 07:19:34

Christopher D. Russell wrote:

> > The requirement, that the input keys should be strictly 
> positive isn't 
> > a big limitation, because it is always possible to accordingly 
> > transform key sets containing possibly negative numbers, ...
> 
> ? By addition of a constant positive offset?

Sure.

> > or to derive the keys from strings to match.
> 
> ? You lost me here. Would you explain this point in a little 
> more detail please.

You're certainly right, that there is no generic and simple way to map
strings to integers besides reinterpreting the bit pattern of the string as
a (probably long) integer. What I've meant is, that sometimes you may use
some simple mapping, for instance adding all the character values of the
string given that these give no collisions for your input key set.

> > The memory requirement for the MPH generator is raising 
> linearily with 
> > the number of keys: roughly N/3 * sizeof(int), where N is 
> the number 
> > of keys.
> 
> ? Is it possible to generalize to keys outside of unsigned 
> int's range w/linear impact on generator performance? 
> Specifically, I'm looking for an efficient hash function for 
> an associative hash table keyed by 16-byte UUID's where I 
> know the set of UUID keys a-priori, hash lookup time is 
> constant (primary consideration), hash generation time is 
> linear (secondary consideration).

This problem is very similar to the string mapping problem you've mentioned
above.
The alogorithm in principle could be applied to integers of arbitrary
precision (given you have a plugin implementation for such a thing, which
could be used in place of the builtin data type), but I'm not able to make
any timing predictions for this. The only thing which seems to be obvious is
that the general dependency from the key set size is still valid.

Regards Hartmut