hash - Why are 5381 and 33 so important in the djb2 algorithm?

Question

The djb2 algorithm has a hash function for strings.

unsigned long hash = 5381;
int c;

while (c = *str++)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

Why are 5381 and 33 so important?

Answer 1

This hash function is similar to a Linear Congruential Generator (LCG - a simple class of functions that generate a series of psuedo-random numbers), which generally has the form:

X = (a * X) + c;  // "mod M", where M = 2^32 or 2^64 typically

Note the similarity to the djb2 hash function... a=33, M=2^32. In order for an LCG to have a "full period" (i.e. as random as it can be), a must have certain properties:

• a-1 is divisible by all prime factors of M (a-1 is 32, which is divisible by 2, the only prime factor of 2^32)
• a-1 is a multiple of 4 if M is a multiple of 4 (yes and yes)

In addition, c and M are supposed to be relatively prime (which will be true for odd values of c).

So as you can see, this hash function somewhat resembles a good LCG. And when it comes to hash functions, you want one that produces a "random" distribution of hash values given a realistic set of input strings.

As for why this hash function is good for strings, I think it has a good balance of being extremely fast, while providing a reasonable distribution of hash values. But I've seen many other hash functions which claim to have much better output characteristics, but involved many more lines of code. For instance see this page about hash functions

EDIT: This good answer explains why 33 and 5381 were chosen for practical reasons.