About

These are a collection of general-purpose hash functions for strings. The string is passed by reference along with the length of the string.

Credits

Robert Sedgwicks

unsigned int RSHash(char* str, unsigned int len) {
    unsigned int a = 63689;
    unsigned int b = 378551;
    unsigned int hash = 0;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = hash * a + (*str);
        a = a * b;
    }
    return hash;
}

Justin Sobel

unsigned int JSHash(char* str, unsigned int len) {
    unsigned int hash = 1315423911;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash ^= ((hash << 5) + (*str) + (hash >> 2));
    }
    return hash;
}

Peter J. Weinberger

unsigned int PJWHash(char* str, unsigned int len) {
    const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
    const unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4);
    const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8);
    const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
    unsigned int hash = 0;
    unsigned int test = 0;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = (hash << OneEighth) + (*str);
 
        if ((test = hash & HighBits) != 0) {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }
    return hash;
}

ELF Hash

Similar to the Peter J. Weinberger hashing function but tweaked for 32-bit processors.

unsigned int ELFHash(char* str, unsigned int len) {
    unsigned int hash = 0;
    unsigned int x = 0;
    for (unsigned int = 0; i < len; str++, i++) {
        hash = (hash << 4) + (*str);
        if ((x = hash & 0xF0000000L) != 0) {
            hash ^= (x >> 24);
        }
        hash &= ~x;
    }
    return hash;
}

Brian Kernighan and Dennis Ritchie

unsigned int BKDRHash(char* str, unsigned int len) {
    unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */
    unsigned int hash = 0;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = (hash * seed) + (*str);
    }
    return hash;
}

SDBM

Used in the Open-Source SDBM project and has a good overall distribution for different data sets. It works well in situations where there is a high variance in the most significant bits of elements in a data set.

unsigned int SDBMHash(char* str, unsigned int len) {
    unsigned int hash = 0;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = (*str) + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
}

Daniel J. Bernstein

unsigned int DJBHash(char* str, unsigned int len) {
    unsigned int hash = 5381;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = ((hash << 5) + hash) + (*str);
    }
    return hash;
}

Donald E. Knuth

unsigned int DEKHash(char* str, unsigned int len) {
    unsigned int hash = len;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
    }
    return hash;
}

Fowler–Noll–Vo


fuss/hash_functions/strings.txt · Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor Access website using i2p


For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.