哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间，且尽可能保证均匀映射。在哈希表中，输入空间是所有 key，输出空间是所有哈希桶（数组索引）。换句话说，对于一个输入 key，可以通过哈希函数得到该 key 在数组中的位置。哈希函数应尽可能保证映射后的输出空间尽可能均匀、分散，以减少哈希冲突的发生。

本文重点分析字符串哈希函数，即输入是字符串的哈希函数。评价 Hash 函数性能的一个重要指标就是冲突，在相关资源允许的条件下冲突越少，Hash 函数的性能就越好。显然，对于字符串哈希函数，尽可能使每个字符都影响哈希值可以减少冲突。

哈希函数性质

具体来说，Hash 函数最重要的性质可以概括为下面两条：

1. 在 Hash 函数值不一样的时候，两个字符串一定不一样；
2. 在 Hash 函数值一样的时候，两个字符串不一定一样（但大概率一样，且我们当然希望它们总是一样的）。

我们将 Hash 函数值一样、但原字符串不一样的现象称为哈希碰撞。

哈希函数设计的关注点：时间复杂度（尽可能低）和 Hash 的准确率（哈希碰撞的概率尽可能低）。

字符串哈希函数

常用字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash 等等。对于以上几种哈希函数，这篇文章 对其进行了一个小小的评测。

• 数据 1 为 100k 个字母和数字组成的随机串哈希冲突个数。
• 数据 2 为 100k 个有意义的英文句子的哈希冲突个数。
• 数据 3 为数据 1 的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。
• 数据 4 为数据 1 的哈希值与 10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较，得出以上平均得分（平均数为平方平均数）。可以发现，BKDRHash 无论是在实际效果还是编码实现中，效果都是最突出的。APHash 也是较为优秀的算法。DJBHash，JSHash，RSHash 与 SDBMHash 各有千秋。PJWHash 与 ELFHash 效果最差，但得分相似，其算法本质是相似的。

PolynomialHash 算法

数学模型：对于一个长度为 $l$ 的字符串 $s$ 来说，可以这样定义多项式 Hash 函数：

$$f(s) = \sum_{i=1}^{l} s[i-1] \times b^{l-i} \bmod M$$

例如，对于字符串 $xyz$，其哈希函数值为 $(xb^{2}+yb+z) \bmod M$。

$M$ 的选择：一个质数（至少要比最大的字符要大），$b$ 可以任意选择。

求解多项式 ：我们可以利用秦九韶算法（又称 Horner 算法）以O(n) 的时间复杂度求解多项式的和。

一般地，一元 $n$ 次多项式的求值需要经过 $\frac{n(n+1)}{2}$ 次乘法和 $n$ 次加法，而秦九韶算法只需要 $n$ 次乘法和 $n$ 次加法。

原多项式公式：

$$f(x) = a_nx^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0$$

秦九韶算法展开式：

$$f(x) = (((\ldots(((a_nx + a_{n-1})x + a_{n-2})x + \ldots)x + a_1)x + a_0$$

实现代码：

1
2
3
4
5
6
7
8
9
10
11

typedef unsigned long long ull;
const unsigned int MOD = 1e9 + 7;  // 用跟元素个数最接近的质数作为散列表的大小

unsigned int PolyHash(const char* s) {
    const unsigned int b = 233;
    unsigned int hash = 0;
    while (*s) {
        hash = ((ull)hash * b + *(s++)) % MOD;  // 秦九韶算法展开式
    }
    return hash;
}

BKDRHash 算法

BKDRHash 算法是由 Brian Kernighan 与 Dennis Ritchie 的《The C Programming Language》一书被展示而得名，是一种简单快捷的 hash 算法，也是 Java 目前采用的字符串的 Hash 算法（累乘因子为 31）。

BKDRHash 算法的 原理是遍历字符串中的每个字符，将前一个字符的哈希值乘以一个固定的素数，然后加上当前字符整形值。最后，对得到的哈希值进行位运算，确保其在特定的整数范围内。

实现代码：

1
2
3
4
5
6
7
8

unsigned int BKDRHash(const char* s) {
    const unsigned int seed = 131;  // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*s) {
        hash = hash * seed + *(s++);
    }
    return hash & 0x7FFFFFFF;
}

BKDRHash 算法和 PolynomialHash 算法并不是同一个算法，但好像很相似。

APHash 算法

Arash Partow 提出了这个算法，声称具有很好地分布性。

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

unsigned int APHash(const char* s) {
    unsigned int hash = 0;

    for (int i = 0; *s; i++) {
        if ((i & 1) == 0) {
            hash ^= ((hash << 7) ^ (*s++) ^ (hash >> 3));
        } else {
            hash ^= (~((hash << 11) ^ (*s++) ^ (hash >> 5)));
        }
    }

    return hash & 0x7FFFFFFF;
}

DJBHash 算法

Daniel J. Bernstein 在 comp.lang.c 邮件列表中发表的，是距今为止比较高效的哈希函数之一。

1
2
3
4
5
6
7
8
9

unsigned int DJBHash(char* str) {
    unsigned int hash = 5381;

    while (*str) {
        hash += (hash << 5) + (*str++);
    }

    return hash & 0x7FFFFFFF;
}

参考资料：

1. https://oi-wiki.org/string/hash/
2. https://blog.csdn.net/wanglx_/article/details/40300363