Thursday, November 3, 2011

Open Question on DJBX33A Hash Function

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.
Post a Comment

2 comments:

Anonymous said...

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

Darmawan Salihun said...

An interesting insight :-).