[boost] Re: [Gauge for interest] Minimal perfect hash function generator

From: Christopher D. Russell (cdr_at_[hidden])
Date: 2005-01-17 06:16:57

Hello Harmut,

This looks useful. I have several questions:

> 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?

> or to derive the keys from strings to match.

? You lost me here. Would you explain this point in a little more detail 
please.

> 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).

- Regards
Chris

"Hartmut Kaiser" <hartmutkaiser_at_[hidden]> wrote in message 
news:1CqRR7-1vg7iS0_at_afwd00.sul.t-online.com...
>
> Hi all,
>
> recently I've written a minimal perfect hash function generator, which
> generates very efficient hashing functions for arbitrary (reasonable large)
> key sets containing strictly positive integers to achieve a minimal and
> perfect mapping of these keys to hash values in the range [0..N), where N 
> is
> the size of the key set (minimality requirement) and the hash values are
> unique (perfection requirement).