为什么是5381和33的djb2算法如此重要？(Why are 5381 and 33 so imp

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

unsigned long hash = 5381;
int c;

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

为什么是5381和33如此重要？

Answer 1:

这个散列函数是类似于线性同余发生器（LCG -一个简单的类的生成的一系列伪随机数的函数），其通常具有以下形式：

X = (a * X) + c;  // "mod M", where M = 2^32 or 2^64 typically

注意相似性的djb2散列函数...一个= 33，M = 2 ^ 32。为了使LCG具有“全周期”（即，随机，因为它可以），一个必须具有某些性能：

A-1是由M的所有素数因子整除（A-1是32，其由2整除，2 ^ 32的唯一主要因素）
A-1是4的倍数，如果M是4的倍数（是的是）

此外，C和M应该是互质（这将是对C的奇数值真）。

因此，大家可以看到，这个哈希函数有点像一个良好的LCG。而且，当涉及到散列函数，你想要一个给定的产生逼真的一组输入字符串的散列值的“随机”分布。

至于为什么这个哈希函数是良好的字符串，我认为它具有极快，同时提供的散列值的合理分布的良好平衡。但我看到那些声称有更好的输出特性，许多其他散列函数，但涉及的更多行代码。比如看到这个网页约散列函数

编辑：这很好的回答解释了为什么33和5381被选为实际原因。

Answer 2:

33的选择是因为：

1）如前文所述，乘法是容易计算使用移位和加法。

2）由于可以从移位看到并添加实现，用33使在散累加器的大部分输入位中的两个副本，然后扩散那些比特相对较远。这有助于产生良好的雪崩。使用较大的转变将复制更少的位，使用更小的转变将保留位相互作用更多本地及会延长为互动传播。

3）的5的移位是相对素32（位在寄存器号码），这与雪崩帮助。虽然有留在字符串中的字符足以，输入字节的每一位最终与输入的每一个前位互动。

4）5的移位考虑ASCII字符数据时是一个很好的移位量。 ASCII字符可以排序的被认为是一个4位的字符类型选择器和一个字符的类型的4位选择器。例如，数字都在第一4位0x3。因此，一个8位移位将具有一定的意义主要是与具有相同的含义其他位相互作用引起位。一个4位或2位的移位将同样产生志趣相投比特之间的强相互作用。 5位的移位导致许多字符的四个低阶位的许多在相同的字符的4个较高位的强烈相互作用。

正如其他地方说，5381的选择不是太重要，许多其他的选择应该在这里工作也是如此。

这不是一个快速哈希函数，因为它处理它输入一个字符的时间和不尝试使用指令级并行。它是，但是，容易写。输出是便于划分编写代码的质量是有可能打一个甜蜜点。

在现代的处理器，乘法是速度远远超过它时，该算法的开发和其他乘法因素（如2 ^ 13 + 2 ^ 5 + 1）可能有类似的表现，稍微好一点的输出，并且能够更加容易的编写。

相反，以上的答案，一个良好的非加密散列函数不希望产生一个随机输出。相反，给定两个输入，几乎是一样的，它要产生广泛不同的输出。如果你输入值是随机分布的，你并不需要一个好的哈希函数，你可以用比特任意一组从您的输入。一些现代的散列函数（詹金斯3，杂音，大概CityHash）产生的输出比随机给定输入，高度相似更好的分布。