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

From: Matthias Troyer (troyer_at_[hidden])
Date: 2005-01-17 03:37:34

On Jan 17, 2005, at 8:34 AM, Hartmut Kaiser wrote:
> 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).
> [...]

> The initial overhead is tolerable, though, here are some timings on my
> machine - Pentium M, 1.6GHz, 1GByte:
>
>       20 keys: 0.005 [s], 200 keys: 0.03 [s], 2000 keys: 0.15 [s], 
> 20000
> keys: 4.45[s]
>
> where the time is raising slightly more worse than linear (actually it 
> has a
> linear and an exponential component, but the exponential component 
> kicks in
> for larger key sets only), depending on the number of keys.
> 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.

I'm very interested if this scales well for a larger number of keys, of 
the order of 10^6 - 10^8 keys. I guess that for those sizes the scaling 
will already be exponential. Can you tell us what the maximum number of 
keys is that can be efficiently treated?

Matthias