DJB2 Hash

What is the djb hash?

The DJB hash (also called DJB2) is a simple and effective hash function created by Daniel J. Bernstein. It’s widely used for hash tables and other applications where you need to quickly convert strings into numeric hash values.

The classic implementation is remarkably simple:

unsigned long hash = 5381;
int c;

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

The algorithm starts with an initial value of 5381, then for each character in the string, it multiplies the current hash by 33 and adds the character’s value. The multiplication by 33 can be optimized as (hash << 5) + hash since shifting left by 5 bits is the same as multiplying by 32.

There’s also a variant called DJB2a that uses XOR instead of addition:

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

Why it works well:

The magic number 33 provides good distribution of hash values
It’s extremely fast, using only shifts, additions, and basic operations
Despite its simplicity, it has relatively low collision rates for typical string data
The initial value 5381 was chosen empirically by Bernstein for good performance

The DJB hash became popular because it offers a sweet spot of simplicity, speed, and “good enough” distribution for many practical applications, though it’s not cryptographically secure and more sophisticated hash functions exist for applications requiring stronger guarantees.

Can you show me a JavaScript implementation?

Here’s a JavaScript implementation of the DJB2 hash function:

function djb2(str) {
    let hash = 5381;
    
    for (let i = 0; i < str.length; i++) {
        const char = str.charCodeAt(i);
        hash = ((hash << 5) + hash) + char; // hash * 33 + char
    }
    
    // Convert to unsigned 32-bit integer
    return hash >>> 0;
}

// Example usage:
console.log(djb2("hello"));        // 210676686835
console.log(djb2("world"));        // 113318802235
console.log(djb2("Hello World"));  // 1415506156816

Key points:

str.charCodeAt(i) gets the Unicode value of each character
hash << 5 shifts the bits left by 5 positions (multiplies by 32)
>>> 0 converts the result to an unsigned 32-bit integer, which is important because JavaScript numbers are 64-bit floats and can represent negative values otherwise

The hash values will be large numbers, so if you need them to fit in a specific range (like for a hash table of size N), you’d typically use djb2(str) % N.

Okay cool. Can you give me 3-5 examples of djb hash usage in the wild in popular programming languages or open source libraries?

Here are some real-world examples of DJB hash usage in popular projects:

1. Lua Programming Language

Lua uses a variant of DJB2 for hashing strings internally. In the Lua source code (lstring.c), you can find:

unsigned int h = cast(unsigned int, l);  /* seed */
size_t step = (l >> 5) + 1;  /* if string is too long, don't hash all its chars */
for (; l >= step; l -= step)
    h = h ^ ((h<<5) + (h>>2) + cast(unsigned char, str[l-1]));

This is used for Lua’s string interning system, where all identical strings share the same memory.

2. Berkeley DB (BDB)

The Berkeley Database library includes DJB hash as one of its hash function options. It’s available as DB_HASH_DJB2 for hash table implementations:

/* DJB hash function - Dan Bernstein */
for (hash = 5381; len--; data++)
    hash = ((hash << 5) + hash) ^ *data;

3. Python’s old `dict` implementation

While Python’s modern dict uses a different algorithm (SipHash for security), older versions and some Python implementations used string hashing similar to DJB:

/* This is the old string hash from Python 2 */
static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;  /* Similar spirit to DJB */
    return x;
}

4. PHP’s hash functions

PHP includes DJB hash as part of its hash() function suite. You can use it directly:

$hash = hash('fnv132', 'hello world');  // FNV is inspired by DJB
// or in older versions, a DJB-style hash for internal string keys

PHP’s internal hash table (used for arrays and objects) historically used DJB-inspired hashing.

5. Redis

Redis uses DJB hash in its implementation of the dict (dictionary) structure for certain hash table operations:

/* Thomas Wang's 32 bit Mix Function */
unsigned int dictGenHashFunction(const void *key, int len) {
    /* Similar to DJB2 approach for string hashing */
    unsigned int hash = 5381;
    
    for (int i = 0; i < len; i++)
        hash = ((hash << 5) + hash) + ((unsigned char *)key)[i];
    
    return hash;
}

Why is DJB so popular?

Simplicity: Easy to implement and understand
Speed: Extremely fast with minimal operations
Good enough: Provides decent distribution for non-adversarial inputs
No dependencies: Requires no lookup tables or complex math