DJB 哈希函数中数字 5381 的原因是什么？

谁能告诉我为什么 DJB 哈希函数中使用数字 5381？

DJB 哈希函数定义为：

• h ₀ = 5381

• h _i = 33h _{i - 1} + s _i

这是一个 C 实现：

unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {   
      hash = ((hash << 5) + hash) + (*str);
   }   

   return hash;
}

我偶然发现了一个comment https://gist.github.com/1676398这让我们对 DJB 的所作所为有了一些了解：

/*
* DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
*
* This is Daniel J. Bernstein's popular `times 33' hash function as
* posted by him years ago on comp.lang.c. It basically uses a function
* like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
* known hash functions for strings. Because it is both computed very
* fast and distributes very well.
*
* The magic of number 33, i.e. why it works better than many other
* constants, prime or not, has never been adequately explained by
* anyone. So I try an explanation: if one experimentally tests all
* multipliers between 1 and 256 (as RSE did now) one detects that even
* numbers are not useable at all. The remaining 128 odd numbers
* (except for the number 1) work more or less all equally well. They
* all distribute in an acceptable way and this way fill a hash table
* with an average percent of approx. 86%.
*
* If one compares the Chi^2 values of the variants, the number 33 not
* even has the best value. But the number 33 and a few other equally
* good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
* advantage to the remaining numbers in the large set of possible
* multipliers: their multiply operation can be replaced by a faster
* operation based on just one shift plus either a single addition
* or subtraction operation. And because a hash function has to both
* distribute good _and_ has to be very fast to compute, those few
* numbers should be preferred and seems to be the reason why Daniel J.
* Bernstein also preferred it.
*
*
* -- Ralf S. Engelschall <[email protected] /cdn-cgi/l/email-protection>
*/

这是一个与您正在查看的哈希函数略有不同的哈希函数，尽管它确实使用了 5381 幻数。链接目标处的注释下方的代码已展开。

然后我发现this http://www.cnblogs.com/napoleon_liu/articles/1911571.html:

Magic Constant 5381:

  1. odd number

  2. prime number

  3. deficient number

  4. 001/010/100/000/101 b

还有this https://stackoverflow.com/a/2854205/63474回答有人可以解释 djb2 哈希函数背后的逻辑吗？ https://stackoverflow.com/questions/1579721/can-anybody-explain-the-logic-behind-djb2-hash-funcition它引用了一个post http://groups.google.com/group/comp.lang.c/browse_thread/thread/9522965e2b8d3809由 DJB 本人发送至提到 5381 的邮件列表（摘自此处摘录的答案）：

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