tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: Perfect hash function generator

On Wed, Jul 15, 2009 at 11:56:49AM +0100, Mindaugas Rasiukevicius wrote:
> Is it a Jenkins lookup3?

No, lookup2. The reason is that the latter version doesn't ensure the
full mixing for all three internal hashes and that makes it a lot less
attractive for using as part of perfect hash functions. It has slightly
higher setup overhead and ~one instruction more per loop, but that is
offset by the advantages.

> Various tests show that it is faster than Jenkins, and good as a general
> purpose hash. Can you deny this, or demonstrate why Jenkins is preferable
> instead of MurmurHash?

It is not the fastest hash if used standalone. It does ensure that you
can get up to three different results with a single pass over the data, which
makes compete with MurmurHash2.

> > The second part is the provided minimal perfect hash function generator.
> > The generated hash function is very simple, using two lookups, a Jenkins
> > hash and three unsigned constant divisions. <...>
> Sounds good, just do we really need this in the base? I think pkgsrc would
> be a better place.

I think the tools used to generate functions in base should be in base
as well.


Home | Main Index | Thread Index | Old Index