hash - 为什么 5381 和 33 在 djb2 算法中如此重要？

Question

djb2 algorithm有一个字符串的哈希函数。

unsigned long hash = 5381;
int c;

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

为什么 5381 和 33 如此重要？

Answer 1

这个哈希函数类似于 Linear Congruential Generator (LCG - 生成一系列伪随机数的简单函数类)，通常具有以下形式:

X = (a * X) + c;  // "mod M", where M = 2^32 or 2^64 typically

请注意与 djb2 哈希函数的相似性...a=33，M=2^32。为了使 LCG 具有“完整周期”(即尽可能随机)，a 必须具有某些属性:

• a-1 可以被 M 的所有质因数整除(a-1 是 32，可以被 2 整除，是 2^32 的唯一质因数)
• 如果 M 是 4 的倍数(是且是)，则 a-1 是 4 的倍数

此外，c 和 M 应该互质(对于 c 的奇数值来说也是如此)。

正如您所看到的，这个哈希函数有点类似于一个好的 LCG。当谈到哈希函数时，您需要一个能够在给定一组实际输入字符串的情况下生成哈希值的“随机”分布的函数。

至于为什么这个哈希函数对字符串有好处，我认为它在速度极快和提供合理的哈希值分布之间取得了很好的平衡。但我见过许多其他哈希函数，它们声称具有更好的输出特性，但涉及更多行代码。例如参见this page about hash functions

编辑:This good answer解释了出于实际原因选择 33 和 5381 的原因。