On Thu, Feb 02, 2012 at 03:31:54PM +0100, Steffen Daode Nurpmeso wrote:
> Otto Moerbeek wrote [2012-02-02 10:43+0100]:
> > Based on Michael's suggestions, I'm now playing with the diff below.
> > It really makes the hastable behave faster.
> >
> > Still have to check if and why more entries than expected are used in
> > some cases.
> >
> > -Otto
> >
> > while (*n != '\0')
> > - h = 2*h + *n++;
> > - return h * 32821; /* scatter bits */
> > + h = 33*h + *n++;
> > + return h;
> > }
>
> I'm using Chris Toreks hash algorithm (as stolen from some
> Berkeley DB source) for more than a decade, after having performed
> quite excessive testing on strings with several hash algorithms.
>
> It is used in general purpose prime-indexed hashtables as well as
> power-of-two spaced (and AND-mask indexed) string-key-only
> dictionaries, and behaves well on all sorts of input ever since
> (using table grow factors from 400% to 1600% percent, normally).
> (Ever since: hmm, in the beginning i've often done
> ::dump_statistics(), but then ..)
>
> So that's what i find in my hash_case.cc:
>
> for (h ^= h; *n; ++n)
> h = (h << 5) + h + (unsigned char)*n;
>
> --steffen
The cast might indeed be needed. For the rest: I think doing things
like h ^= h and writing a multiplication as a shift and addition is
silly: it's the compiler's job to find a good way of computing the
desired values.
-Otto
