常用字符串Hash算法

本文介绍了常用的字符串Hash算法。

杂项算法

杂项哈希算法是从各个地方搜集来的哈希算法。这里只列出几个有名的，所有的可以看参考中的第一条链接。

所有算法最后都需要将hash值限定在哈希表的长度中。这里默认哈希表长度为0x80000000。

BKDRHash

在《C语言程序设计中提出》：

1
2
3
4
5
6
7
8


unsigned int BKDRHash(const char* str) {
    unsigned int seed = 131  // 可以是31, 131, 1313, 13131, ...
    unsigned int hash_code = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return hash & 0x7FFFFFFF;
}

SDBMHash

SDBM项目使用的哈希函数，声称对所有的数据集有很好地分布性。

1
2
3
4
5
6
7


unsigned int SDBMHash(const char* str) {
    unsigned int hash = 0;
    while (*str) {
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    }
    return hash & 0x7FFFFFFF;
}

ELFHash

Unix系统上广泛使用的哈希函数。

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


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

DEKHash

是高德纳在《程序设计艺术》中提出的：

1
2
3
4
5
6
7


unsigned int DEKHash(char* str) {
    int hash = strlen(str);
    while (*str) {
        hash = (hash << 5) ^ (hash >> 27) ^ (*str ++);
    }
    return hash & 0x7FFFFFFF;
}

Java String Hashcode

这是Java的字符串类的Hash算法，简单实用高效。直接从JDK6里面拿出来的代码：

1
2
3
4
5
6
7


unsigned int JDK6Hash(char* str) {
    int hash = 0;
    while (*str) {
        hash = hash * 31 + *str++;
    }
    return hash & 0x7FFFFFFF;
}