djb2 is a simple hashing algorithm and people keep doing it wrong.
tldr; use this
#define ALPHABET \
" !\"#$%&'()*+,-./" \
"0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`" \
"abcdefghijklmnopqrstuvwxyz{|}~"
unsigned long djb2(const char* str) {
unsigned long hash = 0;
unsigned char c;
while ((c = *str++))
hash = hash * 95u + c;
return hash;
}
If you've spent time researching hashmaps and generating hashes from strings you would've stumbled across this function:
Which leaves you with two big questions (maybe three), why 5381? why left-bit-shift 5? (and why a bit-shift and not multiplication?). I'm sure Bernstein has his reasons but I couldn't find them.
The Three Issues
The first issue is that 5381 does nothing. Yes, it literally does nothing interesting to the value. I assumed it helps to roll the value over to help distribute it, but if you think about it for a few minutes that doesn't make any sense. Printable ASCII values range from 32 to 127, so the maximum values with the multiplier is between 172 192 to 683 387 (unsigned long values go to 18446744073709551615).
Assuming you picked the maximum printable ASCII value which is "~" your string would need to be 2.7x10^13 characters long to cause an overflow. Any ideas of "seed" go out the window because the hash doesn't present an avalanche effect.
So it's a bust, might as well make it 0.
The second issue is the magical value of 33. Well this is a bit more interesting and also stupid, I'll get to the latter soon. 33 is just magical, I have no clue why it was picked, a few email threads say it produced a better distribution of values (which I'll get into a towards the end).
Decreasing 33 and checking for collisions yields 0% collisions till we reach 25, where it then jumps up to ~3%. Remember that the lowercase alphabet is 26 characters, ASCII lowercase "a" starts at decimal 97 to "z" which is 122. Calculating 122-97 we get drum roll 25. Which starts to make sense why we find duplicates at 25.
The equation above (simplified) is, x * 25 + c. With some collision math we see that "yz" and "za" produce the same hash of 3147. This is because 25 is equal to the largest difference between "a" and "z", which means there will be more than one way to get to a value. Making the value 26 removes collisions as the upper-bound is larger than the difference.
The third issue, why << 5 + hash is just dumb. The main reason I see people say that we should do this is that "bit shifts are faster", and while yes that is true, they're still adding a value to the shifted value which will still be roughly ~2-3 cycles. Not to mention that a modern compiler generates the same optimized code if we just multiplied by 33 face palm.
Here is the Assembly breakdown, the important thing to look at is the right window, line 10 and 11.
- sal - shift left
- add - add value from x to b
If Optimiser Odis really cared about CPU cycles 32 would be better (only for the lowercase alphabet), that would avoid and extra add and move instruction. So let's just write it in a more human-readable format.
Where are we now?
I've established both 5381 and 33 are random and magical numbers that don't really mean anything. 5381 can be thrown away because seeding a non-avalanching function makes no sense. 33 also has no meaning and writing it as a bit shift does nothing.
If we want a djb2 function that works with all printable ASCII characters with as few collisions as possible we need to pick a value 95. There are 94 typeable characters from a space " " to "~". This leaves us with:
Over 82 317 120 permutations of 4 character string there were 0 collisions.
Final Thoughts
The djb2 most people use doesn't make sense, it doesn't work particularly well and it's more complicated than it needs to be. It doesn't have avalanching nor does 5381 produce fewer collisions. All the reasons I've seen online rationalizing the use of these two numbers still doesn't make much sense.
