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
