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

Djb2算法有一个针对字符串的散列函数。

unsigned long hash = 5381;
int c;


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

为什么5381和33这么重要？

63073 次浏览
小开

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

归功于 杰罗姆 · 伯杰

更新:

这一点似乎得到了当前版本的软件包 djb2的证实: 国家开发银行

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

小开

在5381页，丹 · 伯恩斯坦(djb2)在 这篇文章中说:

[ ... ]几乎所有好的乘数都有效，我觉得你在担心 关于31c + d 没有涵盖任何合理范围的 hash 的事实 如果 c 和 d 在0和255之间，这就是为什么当我发现 33散列函数，并开始使用它在我的压缩器，我开始 散列值为5381。我想您会发现这样做就像 以及261乘数。

整个线程是 给你，如果你感兴趣。

Ozan Yigit 的 关于哈希函数的一页显示:

[ ... ]数字33的魔力(为什么它比许多其他常数(质数或非质数)更好)从来没有得到充分的解释。
小开

这个散列函数类似于 线性同余方法(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。当谈到散列函数时，您需要一个能够产生散列值的“随机”分布的函数，并给出一组实际的输入字符串。

至于为什么这个 hash 函数对字符串有好处，我认为它在提供合理的 hash 值分布的同时具有极快的速度。但是我见过许多其他散列函数，它们声称具有更好的输出特性，但是涉及到更多的代码行。例如，请参阅 关于哈希函数的网页

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

小开

选择33是因为:

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

2)正如你从移位和添加实现中看到的，使用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)比高度相似的随机给定输入产生更好的输出分布。


提交答案