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

该djb2算法对字符串的哈希函数.

unsigned long hash = 5381;
int c;

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

为什么5381和33如此重要？

1> Dustin Boswe..：

---

此哈希函数类似于线性同余生成器(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)

如果M是4的倍数,则a-1是4的倍数(是和是)

另外,c和M应该是相对素数(对于c的奇数值将是真的).

正如您所看到的,此哈希函数有点类似于良好的LCG.当涉及到散列函数时,你需要一个在给定一组输入字符串的情况下产生散列值的"随机"分布的函数.

至于为什么这个哈希函数对字符串很好,我认为它具有非常快的平衡,同时提供合理的哈希值分布.但我已经看到许多其他散列函数声称具有更好的输出特性,但涉及更多的代码行.例如,请参阅有关散列函数的此页面

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

2> Chuck Simmon..：

---

选择33是因为:

1)如前所述,使用shift和add可以很容易地计算乘法.

2)正如您从shift和add实现中看到的那样,使用33会在散列累加器中生成大部分输入位的两个副本,然后将这些位相对较远地分开.这有助于产生良好的雪崩.使用较大的移位会重复较少的位,使用较小的移位会使位交互更加局部化,并使交互扩展需要更长的时间.

3)5的移位相对于32(寄存器中的位数),这有助于雪崩.当字符串中剩余足够的字符时,输入字节的每个位最终将与输入的每个前一位进行交互.

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

如其他地方所述,5381的选择并不太重要,许多其他选择在这里也应该起作用.

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

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

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

3> Matt Curtis..：

---

在5381年,Dan Bernstein(djb2)在这篇文章中说:

[...]几乎任何好的乘数都有效.如果c和d介于0到255之间,我认为你担心31c + d不能覆盖任何合理范围的哈希值.这就是为什么当我发现33哈希函数并开始在我的压缩器中使用它时,我开始的哈希值为5381.我想你会发现这和261乘数一样好.

如果您有兴趣,整个主题就在这里.

Ozan Yigit有一个关于哈希函数的页面,其中说:

[...] 33号的神奇之处(为什么它比许多其他常数更好,无论是否为素数)从未得到充分的解释.

---

注意,散列的起始值(5381)对于相等长度的字符串没有区别,但是在为不同长度的字符串生成不同的散列值时起作用.

4> John Weldon..：

---

也许是因为33 == 2^5 + 1和许多哈希算法2^n + 1用作乘数？

感谢Jerome Berger

更新:

这似乎是由最初来自的软件包djb2的当前版本证实的:cdb

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