djb2算法是一种用于字符串的哈希函数。
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
5381和33为什么这么重要?
这个哈希函数类似于线性同余发生器(LCG - 一种生成一系列伪随机数的简单函数类),通常具有以下形式:
X = (a * X) + c; // "mod M", where M = 2^32 or 2^64 typically
此外,c和M应该是互质的(对于奇数的c来说这是真的)。
因此,您可以看到,这个哈希函数有点像一个好的LCG。当涉及到哈希函数时,您需要一个在给定实际输入字符串集的情况下产生“随机”分布的哈希值的函数。
至于为什么这个哈希函数适用于字符串,我认为它在极快的同时提供了合理的哈希值分布平衡。但我见过很多其他声称具有更好输出特性的哈希函数,但却涉及更多的代码行。例如,请参见关于哈希函数的这个页面
编辑:这个好答案解释了为什么选择33和5381是出于实际原因。
选择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)在给定高度相似的输入时,产生比随机更好的输出分布。
也许是因为33 == 2^n + 1
,而许多哈希算法使用2^n + 1
作为它们的乘数?
更新:
这似乎得到了来自软件包djb2的当前版本的支持:cdb。
我链接的注释描述了哈希算法的核心使用h = ((h << 5) + h) ^ c
进行哈希... x << 5
是一种快速的硬件方式,用2^5作为乘数。
xy
,yX
,z7
。有更好的替代方案。 - Andriy Makukha