hash = n * 0x9e3779b1 >>> 24
为什么使用此特定值？
#1 楼
0x9e3779b9是黄金比例的小数部分0.61803398875…（sqrt（5）-1）/ 2乘以2 ^ 32的整数部分。因此，如果φ=（sqrt（5）+1 ）/ 2 = 1.61803398875是黄金分割率，哈希函数计算n *的小数部分，它具有良好的散射特性。为了说服自己，只需在您最喜欢的电子表格中创建一个(n, n*c-FLOOR(n*c))的散点图，然后用φ，e，π等替换c。 2016/4/29/838。这种方法通常称为“黄金比例哈希”或“斐波那契哈希”，并由Donald Knuth推广（计算机编程艺术：第3卷：排序和搜索）。从理论上讲，它主要归结为Steinhaus猜想（https://en.wikipedia.org/wiki/Three-gap_theorem）和黄金比例φ的倍数小数部分的递归对称性。 >
0x9e3779b9的质数（并且似乎有点“货运邪教”，因为这不是模块化哈希）。同样，0x9e3779b97f4a7c15和0x9e3779b97f4a7c55是这些数字的64位等效项。评论
顺便说一句，与您的答案相反，Linus在您的链接中声称$ \ phi $并不比$ e $或$ \ pi $或“具有合理位分布”的任何常数更好。
–stewbasic
19/12/17在0:58
它永远不是模块化的哈希，而是形式为x％m的哈希。它是一个乘法哈希，如果您使用Knuth建议的其他常量，它仍然是乘法哈希。
–user353249
19/12/17在9:20
好的散射特性实际上并非来自黄金分割率。除了人们试图在黄金中找到神圣的东西超过半千年之外，黄金比例并没有什么内在的魔力。但是，该常数并不比其他常数差，因此可以使用它。此类哈希函数的“魔力”在于将其乘以一个相当大的奇常数，然后向右移动/旋转的组合。它将在两个方向（上下）上分配位。
–达蒙
19/12/17在16:44
阅读实际的Knuth数据源后会得出以下解释（我的第三版中的第517pp页）：解释：对于所有无理数都有一个定理，该定理显示出良好的散射特性，但是一些无理数导致序列更均匀地分布，练习9证明了比率导致“最均匀分布的序列”。因此，是的，关于pi或e也会发挥作用的说法是未经证实的。尽管我猜想它们可能与phi属于同一类别（不过，想要证明或反证的人都会很有趣）。
– Voo
19/12/18在17:59
@Damon这不是真的。黄金分割率是特殊的。这是“最不合理”的数字！这直接与其良好的均布性能有关。参见mathoverflow.net/a/304860。
–user76284
19/12/19在3:30
#2 楼
其他答案解释了这些魔术数字背后的意图，这可能是您想知道的。但是，可以说“它们来自”的地方来自不良的编程实践。幻数是不好的，永远不要使用。诸如上述常量之类的常量应被赋予适当的描述性变量名称，甚至应在其定义位置添加注释。然后，代码中值的每次出现都应采用命名变量的形式。如果您在满足这些值的代码中遇到这种情况，那么您一开始就不会因它们的意图而感到困惑。示例：
错误示例-使用魔术数字
hash = n * 0x9e3779b1
更好的例子-带注释和有意义的变量
# Golden Ratio constant used for better hash scattering
# See https://softwareengineering.stackexchange.com/a/402543
GOLDEN_RATIO = 0x9e3779b1
hash = n * GOLDEN_RATIO
评论
“魔术数字不好，永远不要使用。”绝对的一般性陈述几乎总是错误的。出于某些良好的原因，请参阅crypto.stackexchange.com/a/76301 AES使用幻数。
–邓肯X辛普森
19/12/16在19:53
@DuncanXSimpson链接的答案主要是错误的，并且显然是由不编写代码的人编写的。关于参数化的第一点是正确的，但是这个答案并不表明这一点。至于链接答案中的其他两点，它们完全是错误的。所有现代编程语言都提供了一些用于设置常量值的机制，并且大多数编译器还可以优化不变的变量值。被链接的问题中的链接代码甚至会使用带有解释性注释的常量值，以无视该错误答案。
–格雷厄姆
19/12/16在22:56
@Graham我认为您和Duncan在使用“魔术数”这个词时会用不同的语言，并且彼此交谈。您和i硅烷正在讨论如何在代码中表达算法；特别是源代码是否明确了使用特定值的原因。这对行为没有影响。链接的问题（可能会误用短语“魔数”）是关于更改加密算法的行为，使这些值参数作为输入而不是常量提供。有了这种理解，答案中的三点才有意义。
–stewbasic
19/12/17在0:47
“绝对的一般性陈述几乎总是错误的。”但愿如此。例如，绝对通用语句为false的绝对通用语句为false（您可能在发送评论之前就意识到了这一点，并添加“几乎”以免使您的回答具有讽刺意味）。有些事情总是错误的，例如代码中的魔术数字（意味着无法解释的任意值）：）
–硅烷
19/12/17在7:42
只有西斯绝对！
– NKCampbell
19/12/17在14:52
#3 楼
在处理哈希表的代码中，我经常发现常量0x9e3779b9或有时为0x9e3779b1
另一个答案正确地解释了为什么使用此值。但是，如果您经常发现此常数，则可能没有意识到自己经常会发现容易受到哈希洪泛攻击的代码。
有两种针对哈希洪泛攻击的策略：
使用具有秘密随机种子的安全哈希函数。您的哈希函数没有秘密的随机种子。 Murmurhash3_32有一个秘密的随机种子，但是由于内部状态小，它具有与种子无关的多重碰撞。具有近乎密码安全性且仍几乎可接受的性能的最佳哈希函数可能是SipHash。不幸的是，它很慢，尽管不如SHA512等慢。平衡二叉搜索树。因此，普通的单独链接的哈希表将每个存储桶都作为一个链表，如果将很多值哈希到相同的存储桶，这将很慢。通过使它成为平衡的二叉搜索树（例如AVL树或红黑树），您仍然可以保证在最坏情况下的性能。
我的观点是（2）更好，因为SipHash如此之慢。同样，在操作系统内核空间中，可能没有足够的熵来在启动阶段的早期创建秘密的随机种子，因此在内核空间中，您可能没有能力在启动初期的早期创建随机数。 />哈希表被广泛滥用。仅通过发送散列到同一存储桶中的许多值，很容易使许多系统停机，
评论
请注意，哈希表每次增长时都可以重新播种一个随机种子-因此，即使在启动时内核也没有熵可借鉴，只要以后发生攻击就没有问题。
– Matthieu M.
19/12/16在12:38
@MatthieuM。假设您接受哈希表增长操作的延迟。在许多情况下，内核无法接受该值，而是根据计算机中的内存量将哈希表大小设置为固定值。
– juhist
19/12/16在12:39
如果这是一个问题，也可以解决：线性重新散列（触发冲突次数触发）将允许重新播种-您只需要在过渡期间进行两次查找即可。总的来说，我确实更喜欢线性重新哈希，但是哈希映射实现通常针对吞吐量而不是延迟进行调整
– Matthieu M.
19/12/16在12:46
阿们就容易计算。通常，mod作为子字符串或高阶截断并不容易。如果仅平衡队列或生成合成密钥，则安全性和种子设定通常无关紧要。可能永远不需要再次计算。
–mckenzm
19/12/18在22:34
评论
使用此常数的一些特定的代码引用将很有帮助。例如，我在SQLite中找到它。