RE: [boost] [Gauge for interest] Minimal perfect hashfunctiongenerator

From: Hartmut Kaiser (hartmutkaiser_at_[hidden])
Date: 2005-01-19 15:16:22

Hurd, Matthew wrote:

> The University of Auckland does not have the Uzgalis, Todd 
> technical report "Hashing Myths" online.
> 
> An overview presentation that is enough to get going is here:
> 	http://www.iticse2002.dk/conference/sessionmat/algorithms/1.pdf
> 
> >From the first slide: 
> 
>     The work presented here is almost entirely
>     due to Robert Uzgalas ("Buz"), who single
>     handedly reinvented hashing in the early
>     1990s.
> 
>     For reasons unknown, Robert never
>     disseminated his work to the wide audience
>     that it deserved. His paper, "Hashing Myths"
>     remains unpublished, and his results are
>     virtually unknown.
> 
> Here is a snippet related by one of the authors, R. Uzgalis
> 	http://www.serve.net/buz/hash.adt/java.000.html

Thanks for the pointers!

I'm currently working on another type of MPH function generator, which is
based on stochastic functions and seems to provide minimal perfect hash
functions for strings even for large key sets (> 10e6 keys). The drawback
will be, that the hashing function is O(n) with respect to the number of
keys. 

This technique additionally allows to map strings (or other byte sequences)
to unique integers, which I'll try to incorporate as a complement to the MPH
I've described earlier. These integers then yould be used to construct the
MPH. Again this has the drawback of a hashing function with is O(n) this
time with respect to the key length.

Regards Hartmut