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

EN

此散列函数类似于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-1可以被M的所有素因数整除(a-1是32，它可以被2整除，这是2^32的唯一素因数)
• a-1是4的倍数，如果M是4的倍数(是和是)

此外，c和M被认为是相对质数(对于c的奇数值也是如此)。

如你所见，这个散列函数有点像一个很好的LCG。当涉及到哈希函数时，您需要一种在给定一组真实的输入字符串的情况下生成哈希值的“随机”分布的哈希函数。

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

编辑：This good answer解释了为什么选择33和5381是出于实际原因。

选择33是因为：

1)如前所述，使用移位和加法很容易计算乘法。

2)正如您从shift和add实现中看到的，使用33将散列累加器中的大部分输入位复制为两个副本，然后将这些位分散到相对较远的位置。这有助于产生良好的雪崩。使用较大的移位将复制较少的比特，使用较小的移位将使比特交互更具局部性，并使交互传播的时间更长。

3) 5的移位相对质数为32 (寄存器中的位数)，这有助于雪崩。虽然字符串中还有足够的字符，但输入字节的每一位最终都会与前面的每一位输入进行交互。

4)在考虑ASCII字符数据时，5的移位量是一个很好的移位量。ASCII字符可以看作是一个4位字符类型选择器和一个4位字符类型选择器。例如，所有数字的前4位都有0x3。因此，8位移位将导致具有特定含义的位主要与具有相同含义的其他位交互。4位或2位移位同样会在志同道合的位之间产生强烈的交互作用。5位移位导致字符的四个低位中的许多位与同一字符中的许多四位高位强烈交互。

正如前面所说的，5381的选择并不太重要，许多其他的选择在这里应该也可以。

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

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

与上面的答案相反，一个好的非加密散列函数不想产生随机输出。相反，给定两个几乎相同的输入，它希望产生完全不同的输出。如果你的输入值是随机分布的，你不需要一个好的哈希函数，你可以只使用输入中的任意一组位。一些现代散列函数(Jenkins 3，Murmur，可能是CityHash)比高度相似的随机给定输入产生更好的输出分布。

在5381，丹·伯恩斯坦(djb2)在this article中说

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

如果你感兴趣的话，整个线程都是here。

Ozan Yigit有一个a page on hash functions，上面写着：

...数字33的魔力(为什么它比许多其他常量更好，不管是不是素数)一直没有得到充分的解释。