Home
The Simplest String Hash Function: djb2 Algorithm and Implementations

The Simplest String Hash Function: djb2 Algorithm and Implementations

August 5, 2024 No Comments algorithms, BASH, c / c++, c #, C/C++, C# (CSharp), Go, Go Programming, Hashing, java, Java, javascript, Node.Js, PHP, php, programming languages, Python, Rust

A simple yet effective hash function for strings is the well-known “djb2” algorithm by Daniel J. Bernstein. It is simple to implement and has good performance characteristics for many use cases.

C++ djb2 Hash Function

Here is the implementation of the djb2 hash function in C++:

1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>
#include <string>
 
unsigned long djb2(const std::string &str) {
    unsigned long hash = 5381;
    for (char c : str) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}
 
Example usage:
#include <iostream>
#include <string>

unsigned long djb2(const std::string &str) {
    unsigned long hash = 5381;
    for (char c : str) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

Example usage:
1
2
3
4
5
6
7
8
9
10

int main() {
    std::string input;
    std::cout << "Enter a string to hash: ";
    std::getline(std::cin, input);
 
    unsigned long hashValue = djb2(input);
    std::cout << "Hash value: " << hashValue << std::endl;
 
    return 0;
}
int main() {
    std::string input;
    std::cout << "Enter a string to hash: ";
    std::getline(std::cin, input);

    unsigned long hashValue = djb2(input);
    std::cout << "Hash value: " << hashValue << std::endl;

    return 0;
}

Explanation of djb2 hash function

  • unsigned long hash = 5381; initializes the hash value to 5381. This seed value was chosen by Bernstein as it provides good distribution properties.
  • The loop for (char c : str) iterates over each character in the input string.
  • hash = ((hash << 5) + hash) + c; updates the hash value. The expression (hash << 5) + hash is equivalent to hash * 33 (left shift by 5 is the same as multiplying by 32, and then adding the original hash gives 33 times the hash). Adding the current character c incorporates it into the hash.

This function will take a string and produce an unsigned long hash value, which can be used for various purposes such as hash tables, checksums, etc.

Here are the implementations of the djb2 hash function in various programming languages:

C implementation of djb2 Hash Function

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>
 
unsigned long djb2(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}
#include <stdio.h>

unsigned long djb2(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

Example Usage:

1
2
3
4
5
6
7
8
9
10

int main() {
    char input[256];
    printf("Enter a string to hash: ");
    fgets(input, 256, stdin);
 
    unsigned long hashValue = djb2(input);
    printf("Hash value: %lu\n", hashValue);
 
    return 0;
}
int main() {
    char input[256];
    printf("Enter a string to hash: ");
    fgets(input, 256, stdin);

    unsigned long hashValue = djb2(input);
    printf("Hash value: %lu\n", hashValue);

    return 0;
}

Python implementation of djb2 Hash Function

1
2
3
4
5
6
7
8

def djb2(s):
    hash = 5381
    for c in s:
        hash = ((hash << 5) + hash) + ord(c)  # hash * 33 + ord(c)
    return hash
 
input_str = input("Enter a string to hash: ")
print("Hash value:", djb2(input_str))
def djb2(s):
    hash = 5381
    for c in s:
        hash = ((hash << 5) + hash) + ord(c)  # hash * 33 + ord(c)
    return hash

input_str = input("Enter a string to hash: ")
print("Hash value:", djb2(input_str))

Go implementation of djb2 Hash Function

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func djb2(str string) uint64 {
    hash := uint64(5381)
    for _, c := range str {
        hash = ((hash << 5) + hash) + uint64(c)  // hash * 33 + c
    }
    return hash
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    fmt.Print("Enter a string to hash: ")
    input, _ := reader.ReadString('\n')
    input = strings.TrimSpace(input)
    
    hashValue := djb2(input)
    fmt.Printf("Hash value: %d\n", hashValue)
}

Rust implementation of djb2 Hash Function

use std::io::{self, Write};

fn djb2(s: &str) -> u64 {
    let mut hash = 5381;
    for c in s.chars() {
        hash = ((hash << 5) + hash) + c as u64;  // hash * 33 + c
    }
    hash
}

fn main() {
    print!("Enter a string to hash: ");
    io::stdout().flush().unwrap();
    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("Failed to read line");
    let input = input.trim();

    let hash_value = djb2(input);
    println!("Hash value: {}", hash_value);
}

Java implementation of djb2 Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import java.util.Scanner;
 
public class Djb2Hash {
    public static long djb2(String str) {
        long hash = 5381;
        for (int i = 0; i < str.length(); i++) {
            hash = ((hash << 5) + hash) + str.charAt(i);  // hash * 33 + c
        }
        return hash;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a string to hash: ");
        String input = scanner.nextLine();
 
        long hashValue = djb2(input);
        System.out.println("Hash value: " + hashValue);
    }
}
import java.util.Scanner;

public class Djb2Hash {
    public static long djb2(String str) {
        long hash = 5381;
        for (int i = 0; i < str.length(); i++) {
            hash = ((hash << 5) + hash) + str.charAt(i);  // hash * 33 + c
        }
        return hash;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a string to hash: ");
        String input = scanner.nextLine();

        long hashValue = djb2(input);
        System.out.println("Hash value: " + hashValue);
    }
}

C# implementation of djb2 Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

using System;
 
class Djb2Hash
{
    public static ulong Djb2(string str)
    {
        ulong hash = 5381;
        foreach (char c in str)
        {
            hash = ((hash << 5) + hash) + (ulong)c;  // hash * 33 + c
        }
        return hash;
    }
 
    static void Main()
    {
        Console.Write("Enter a string to hash: ");
        string input = Console.ReadLine();
 
        ulong hashValue = Djb2(input);
        Console.WriteLine("Hash value: " + hashValue);
    }
}
using System;

class Djb2Hash
{
    public static ulong Djb2(string str)
    {
        ulong hash = 5381;
        foreach (char c in str)
        {
            hash = ((hash << 5) + hash) + (ulong)c;  // hash * 33 + c
        }
        return hash;
    }

    static void Main()
    {
        Console.Write("Enter a string to hash: ");
        string input = Console.ReadLine();

        ulong hashValue = Djb2(input);
        Console.WriteLine("Hash value: " + hashValue);
    }
}

PHP implementation of djb2 Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<?php
function djb2($str) {
    $hash = 5381;
    for ($i = 0; $i < strlen($str); $i++) {
        $hash = (($hash << 5) + $hash) + ord($str[$i]);  // hash * 33 + ord(c)
    }
    return $hash;
}
 
echo "Enter a string to hash: ";
$input = trim(fgets(STDIN));
 
$hashValue = djb2($input);
echo "Hash value: " . $hashValue . "\n";
?>
<?php
function djb2($str) {
    $hash = 5381;
    for ($i = 0; $i < strlen($str); $i++) {
        $hash = (($hash << 5) + $hash) + ord($str[$i]);  // hash * 33 + ord(c)
    }
    return $hash;
}

echo "Enter a string to hash: ";
$input = trim(fgets(STDIN));

$hashValue = djb2($input);
echo "Hash value: " . $hashValue . "\n";
?>

Javascript/Js/NodeJs implementation of djb2 Hash Function

1
2
3
4
5
6
7
8
9
10
11

function djb2(str) {
    let hash = 5381;
    for (let i = 0; i < str.length; i++) {
        hash = ((hash << 5) + hash) + str.charCodeAt(i);  // hash * 33 + c
    }
    return hash >>> 0;  // Convert to unsigned 32-bit integer
}
 
const input = prompt("Enter a string to hash:");
const hashValue = djb2(input);
console.log("Hash value:", hashValue);
function djb2(str) {
    let hash = 5381;
    for (let i = 0; i < str.length; i++) {
        hash = ((hash << 5) + hash) + str.charCodeAt(i);  // hash * 33 + c
    }
    return hash >>> 0;  // Convert to unsigned 32-bit integer
}

const input = prompt("Enter a string to hash:");
const hashValue = djb2(input);
console.log("Hash value:", hashValue);

BASH implementation of djb2 Hash Function

Implementing the djb2 hash function in Bash is more complex due to its limited support for bitwise operations and integer handling. However, we can achieve this using external commands like bc for arithmetic operations.

Here is a Bash script implementing the djb2 hash function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#!/bin/bash
 
djb2() {
    local str="$1"
    local hash=5381
    local char
 
    for (( i=0; i<${#str}; i++ )); do
        char=$(printf "%d" "'${str:$i:1}")
        hash=$(echo "(( $hash << 5 ) + $hash) + $char" | bc)
    done
 
    echo $hash
}
 
read -p "Enter a string to hash: " input
hash_value=$(djb2 "$input")
echo "Hash value: $hash_value"
#!/bin/bash

djb2() {
    local str="$1"
    local hash=5381
    local char

    for (( i=0; i<${#str}; i++ )); do
        char=$(printf "%d" "'${str:$i:1}")
        hash=$(echo "(( $hash << 5 ) + $hash) + $char" | bc)
    done

    echo $hash
}

read -p "Enter a string to hash: " input
hash_value=$(djb2 "$input")
echo "Hash value: $hash_value"

Explanation:

  • local str=”$1″: Assigns the first argument of the function to the variable str.
  • local hash=5381: Initializes the hash value to 5381.
  • The for loop iterates over each character in the input string.
  • char=$(printf “%d” “‘${str:$i:1}”): Converts the character to its ASCII value.
  • hash=$(echo “(( $hash << 5 ) + $hash) + $char” | bc): Updates the hash value using bc for arithmetic operations.

Save this script to a file, for example djb2.sh, and make it executable with chmod +x djb2.sh. You can then run it in a terminal to test it:

Another BASH Implementation without the bc utility.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#!/bin/bash
 
djb2() {
    local str="$1"
    local hash=5381
    local char
 
    for (( i=0; i<${#str}; i++ )); do
        char=$(printf "%d" "'${str:$i:1}")
        hash=$(( (hash << 5) + hash + char ))
    done
 
    # Handle potential overflow by masking to a 32-bit integer
    hash=$((hash & 0xFFFFFFFF))
 
    echo $hash
}
 
read -p "Enter a string to hash: " input
hash_value=$(djb2 "$input")
echo "Hash value: $hash_value"
#!/bin/bash

djb2() {
    local str="$1"
    local hash=5381
    local char

    for (( i=0; i<${#str}; i++ )); do
        char=$(printf "%d" "'${str:$i:1}")
        hash=$(( (hash << 5) + hash + char ))
    done

    # Handle potential overflow by masking to a 32-bit integer
    hash=$((hash & 0xFFFFFFFF))

    echo $hash
}

read -p "Enter a string to hash: " input
hash_value=$(djb2 "$input")
echo "Hash value: $hash_value"

Explanation:

  • local hash=5381: Initializes the hash value.
  • for (( i=0; i<${#str}; i++ )); do: Loops through each character in the string.
  • char=$(printf “%d” “‘${str:$i:1}”): Converts the character to its ASCII value.
  • hash=$(( (hash << 5) + hash + char )): Computes the hash value with Bash arithmetic.
  • hash=$((hash & 0xFFFFFFFF)): Ensures the hash fits within a 32-bit integer to avoid overflow issues.
  • Finally, echo $hash prints the hash value.

Save this script to a file, make it executable, and run it as before:

1
2

chmod +x djb2.sh
./djb2.sh
chmod +x djb2.sh
./djb2.sh

These implementations follow the same logic of the djb2 hash function and should work similarly across these languages.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1349 words
Last Post: Hot Weather Causes Intel CPU Throttle and NVidia GPU Crashes on Windows 11 (Blue Screen)
Next Post: Teaching Kids Programming - Minimum Increment to Make Array Unique (Sorting/Greedy)

The Permanent URL is: The Simplest String Hash Function: djb2 Algorithm and Implementations

Related posts:

  1. Teaching Kids Programming – Algorithmic Runtime and Space Complexity Teaching Kids Programming: Videos on Data Structures and Algorithms We analyse an algorithm for its...
  2. Pointer Arithmetic in Delphi Delphi is based on Object Pascal, which is a great programming language. Delphi is also...
  3. How to Kill a Process That Opens a TCP/UDP Port? Killing a process that opens a TCP port can be necessary in various situations, such...
  4. How to Evaluate Reverse Polish Notation using Stack? Polish notation/expression is also known as ‘prefix notation’ where the numbers are preceded by its...
  5. Interview Coding Exercise – Nested String (Python) Nested String A string S consisting of N characters is considered to be properly nested...
  6. Tutorial 1 – C Programming for 6502 (8 bit) CPU 6502 CPUs were a massive success back in the 80s and early 90s. The 6502...
  7. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  8. Providing an IsUnicodeVersion API in Your Delphi Project I have recently migrated my project from Delphi 2007 to Delphi XE8 (and Seattle). It...

Leave a Reply