Where did Daniel J. Bernstein obtain his 33 constant in the DJBX33A hash function?
As we know the DJBX33A (Daniel J. Bernstein "Times 33 Addition") algorithm works like this:
hash_t bernstein_hash(const unsigned char *key)
{
hash_t h=0;
while(*key) h=33*h + *key++;
return h;
}
[Code snippet courtesy of
http://en.literateprograms.org/Hash_function_comparison_(C,_sh)]. I wonder if the value was obtained from some sort of mathematical formulae or based results of numerous experiments?
Well, yeah. Hashing is still a sort of black-art even now. But, I think there should be some sort of logical explanation.
2 comments:
33=32+1, so multiplication of x by 33 can be efficiently implemented as (x<<5)+x
I'd imagine he did a few tests with a given data set, and checked which factor gave the best results
An interesting insight :-).
Post a Comment