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

by

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.

More Related Contents:

  1. Is it possible to decrypt MD5 hashes?
  2. Are mutable hashmap keys a dangerous practice?
  3. How does password salt help against a rainbow table attack?
  4. Salting Your Password: Best Practices? [closed]
  5. Is it safe to ignore the possibility of SHA collisions in practice?
  6. Probability of SHA1 collisions
  7. Are there any SHA-256 javascript implementations that are generally considered trustworthy? [closed]
  8. Is there an MD5 Fixed Point where md5(x) == x?
  9. yii CPasswordHelper: hashPassword and verifyPassword
  10. How come MD5 hash values are not reversible?
  11. Is calculating an MD5 hash less CPU intensive than SHA family functions?
  12. When is CRC more appropriate to use than MD5/SHA1?
  13. How long to brute force a salted SHA-512 hash? (salt provided)
  14. Can two different strings generate the same MD5 hash code?
  15. How are hash functions like MD5 unique?
  16. Why is ‘397’ used for ReSharper GetHashCode override?
  17. Is MD5 still good enough to uniquely identify files?
  18. Why are XOR often used in java hashCode() but another bitwise operators are used rarely?
  19. How can it be impossible to “decrypt” an MD5 hash? [duplicate]
  20. Is it possible to decrypt MD5 hashes?
  21. How to “EXPIRE” the “HSET” child key in redis?
  22. node.js hash string?
  23. Best practice for hashing passwords – SHA256 or SHA512?
  24. Is “double hashing” a password less secure than just hashing it once?
  25. Is SHA-1 secure for password storage?
  26. Compile time string hashing
  27. Converting a nested hash into a flat hash
  28. Is there an IDictionary implementation that, on missing key, returns the default value instead of throwing?
  29. Storing SHA1 hash values in MySQL
  30. php: number only hash?

Leave a Comment