Re: hash
Lew wrote:
b...@coolgroups.com wrote:
Any ideas where they got the magic number 31 that is being used in the
formula?
Donald Knuth, /The Art of Computer Programming/, volume 3, Sorting and
Searching, pp. 506?542.
Tom Anderson wrote:
Dan Bernstein.
Seriously. Daniel J. Bernstein invented a very popular hash function,
known as djb, which is just like the java string hash, but with a
multiplier of 33 instead of 31. 33 and 31 work similarly, in that
multiplying a binary number by them is like shifting it left five bits and
then either adding or subtracting the original; that gives you five bits
of diffusion, but keeps some influence of the original value over the
bottom bit of the hash (does that make sense?).
Strange, but I can find no mention of the number thirty-one
in that section. In particular, the two paragraphs devoted to
the matter of hashing multiword keys (which is what String's
hashcode() is really doing) do not mention it.
It's obvious that the chosen multiplier must be odd, because
if it were even the leading characters of a String longer than
thirty-two bits would have no influence on the result. But if
there's a reason the multiplier should be prime, it's a reason
I've never heard explained. Lots of numerology surrounds hash
schemes; perhaps thirty-one is just another bit of folklore?
I don't know why Sun went with 31 over 33.
Probably because Knuth blessed that value as being one that was
studied and found to suffice.
Can you cite the blessing, with a locator somewhat
tighter than a range of thirty-seven pages?
--
Eric Sosman
esosman@ieee-dot-org.invalid