为什么在djb2算法中，5381和33很重要？

Question

djb2算法是一种用于字符串的哈希函数。

unsigned long hash = 5381;
int c;

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

5381和33为什么这么重要？

- Vishnu Pedireddi

---

可能是DJB哈希函数中使用5381数字的原因？的重复问题。 - rob mayoff

尽管DJB2算法在哈希生成中表现不佳。例如，它对于这些字符串返回相同的哈希值：xy，yX，z7。有更好的替代方案。 - Andriy Makukha

Answer 1

这个哈希函数类似于线性同余发生器（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。当涉及到哈希函数时，您需要一个在给定实际输入字符串集的情况下产生“随机”分布的哈希值的函数。

至于为什么这个哈希函数适用于字符串，我认为它在极快的同时提供了合理的哈希值分布平衡。但我见过很多其他声称具有更好输出特性的哈希函数，但却涉及更多的代码行。例如，请参见关于哈希函数的这个页面

编辑：这个好答案解释了为什么选择33和5381是出于实际原因。

- Dustin Boswell

Answer 2

选择33的原因：

1) 如前所述，使用移位和加法可以轻松计算乘法。

2) 从移位和加法实现可以看出，使用33会将哈希累加器中大多数输入位的副本复制两份，然后将这些位分散得相对较远。这有助于产生良好的avalanching效果。使用更大的移位会复制较少的位，使用更小的移位会使位交互更加局部化，并且需要更长时间才能使交互扩散。

3) 移位5相对于寄存器中32（位数）是互质的，这有助于avalanching。当字符串中还有足够的字符时，每个输入字节的每个位最终都会与其前面的所有位交互。

4) 对于ASCII字符数据，移位5是一个很好的移位量。可以将ASCII字符视为4位字符类型选择器和4位字符类型选择器。例如，所有数字在前4位中都具有0x3。因此，8位移位会导致具有特定含义的位主要与具有相同含义的其他位交互。4位或2位移位同样会在类似思想的位之间产生强烈的交互。5位移位会导致字符的低4位与同一字符的4个高位之间产生强烈的交互。

如其他地方所述，选择5381并不太重要，因为许多其他选择在这里也应该起作用。

这不是一个快速的哈希函数，因为它以字符为单位处理其输入，并且不尝试使用指令级并行性。然而，编写代码易于操作。输出质量除以编写代码的难度很可能达到一个最佳点。

在现代处理器上，乘法比该算法开发时更快，其他乘法因子（例如2 ^ 13 + 2 ^ 5 + 1）可能具有相似的性能，略微更好的输出，并且略微更易于编写。

与上面的答案相反，一个好的非加密哈希函数不需要产生随机输出。相反，如果给出两个几乎相同的输入值，它想要产生大不相同的输出。如果你的输入值是随机分布的，你就不需要一个好的哈希函数，你可以直接使用输入中任意一组比特位。一些现代哈希函数（如 Jenkins 3、Murmur、可能是 CityHash）在给定高度相似的输入时，产生比随机更好的输出分布。

- Chuck Simmons

---

这个回答实际上回答了问题。谢谢！ - Erik Aronesty

Answer 3

在5381年，丹·伯恩斯坦（djb2）在这篇文章中说：

[...] 实际上任何良好的乘数都可以使用。我认为你担心的是如果c和d在0到255之间，31c + d无法覆盖任何合理范围的哈希值。这就是为什么当我发现33个哈希函数并开始在我的压缩程序中使用它时，我从哈希值5381开始。我认为你会发现，这与261个乘法器一样有效。

整个讨论线程在这里，如果您有兴趣的话。

Ozan Yigit在这个哈希函数页面中表示：

[...] 数字33的神奇之处（它为什么比许多其他常数，无论是否为质数，都表现得更好）从未得到充分解释。

- Matt Curtis

---

请注意，哈希的起始值（5381）对于相等长度的字符串没有影响，但会在生成不同长度字符串的哈希值时发挥作用。 - yoyo

Answer 4

也许是因为33 == 2^n + 1，而许多哈希算法使用2^n + 1作为它们的乘数？

感谢Jerome Berger。

更新：

这似乎得到了来自软件包djb2的当前版本的支持：cdb。

我链接的注释描述了哈希算法的核心使用h = ((h << 5) + h) ^ c进行哈希... x << 5是一种快速的硬件方式，用2^5作为乘数。

- John Weldon