算法与计算机科学probablydance.com
斐波那契哈希：被世界遗忘的优化
Fibonacci Hashing: The Optimization That the World Forgot
2018 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章介绍斐波那契哈希（用黄金比例常数做乘法再取高位）作为把哈希值映射到 2 的幂大小哈希表索引的方法，认为它比常见的取模运算更快，且分布更均匀。作者给出了性能测量和背后的数论解释。
为什么经久不衰：它揭示了一个被主流标准库（GCC、LLVM、Boost）忽视的简单优化，兼具理论趣味和工程价值，多年来反复引发讨论。
HN 评论精选
MurmurHash 作者警告：斐波那契哈希不能弥补弱哈希函数的碰撞问题，应优先用好的哈希函数加位掩码。
别这么做。应该用能保证高度随机分布的真正哈希函数，让哈希表大小为 2 的幂，然后用 (hash & (size-1)) 把哈希值映射到表索引。斐波那契常数只能改善劣质哈希函数的分布，但如果底层哈希函数本身弱，它对抗碰撞性毫无帮助。——MurmurHash 和 SMHasher 的作者 Austin
aappleby查看英文原文
Don't do this. Use a real hash function that guarantees a highly random distribution, make your hash tables power-of-two sized, and map from hash value to table index using (hash & (size-1)). The fibonacci constant thing will help clean up the distribution of a bad hash function, but it does nothing for collision resistance if the underlying hash function is weak. -Austin, author of Murmurhash and SMHasher
与标准库对比不公平，但主流库用取模确实慢；快速哈希表通常用异或混合低位即可。
拿自定义实现和需要完全通用的标准 unordered_map 比较并不公平。不过我仍然很惊讶 GCC、LLVM 和 Boost 都用取模来分配桶，这非常慢，很想知道原因。我原以为它们会用高位掩码（或与表大小做与运算）。快速哈希表用异或来混合低位信息（例子见下）。斐波那契哈希相当于对输入再跑一遍乘法哈希，只有对输入分布偏执时才值得。Java SDK 和 Android 的实现都用了异或混合。
allenz查看英文原文
It's not really fair to compare a custom implementation against the standard unordered_map implementations, which need to be fully general. See https://news.ycombinator.com/item?id=9675608 Still, I'm shocked that GCC, LLVM, and boost all assign buckets using modulus, which is very slow. I would love to know the reasoning. I assumed that they mask the high bit (or & with the table size). Fast hashmaps use xor to mix information from low bits (examples below). Fibonacci hashing amounts to running a second multiplicative hash over your input, which is only worthwhile if you're paranoid about your input distribution. Java SDK: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l320 Android (C++): https://android.googlesource.com/platform/system/core/+/master/libcutils/hashmap.cpp#83
文章顺带提到的'下移后异或'可能本身就足够好，作者却没单独测试它。
总结：文章想找把哈希码高效映射到 2 的幂大小范围的方法。它否定了常见的截高位做法（因为丢弃信息），提出斐波那契哈希：乘以黄金比例再下移。文中给出了性能测量和理论解释。但文章后来顺带提到一个更简单的做法：把高位下移再异或！作者只是把它作为斐波那契哈希的前置步骤来避免坏模式。我不禁想：下移异或本身是不是就够用了？
rntz查看英文原文
Summary: The article is looking for an efficient way to map a hash code into a smaller power-of-two-sized range, for use as a hashtable index. It dismisses the common solution, masking off the high bits, because it discards information, and proposes Fibonacci hashing: multiply by the golden ratio and shift down. It gives measurements suggesting this gives better performance in practice, and some theory as to why this might be. But later it mentions, in passing, a simpler approach: just shift the high bits down and xor! The author only tries doing this as a preprocessing step in front of Fibonacci hashing to avoid "bad patterns". So I'm left wondering: might shift-down-and-xor be good enough on its own?
从 LCG 角度审视黄金比例常数，其二进制模式未必最优，Knuth 找的乘数可能更好。
黄金比例本质上是线性同余伪随机数生成的一个特殊乘数，我不确定它的非重复特性是否真能带来性能收益。2^64 / 1.618 的常数 11400714819323198486 的二进制表示里有 7 个连续的 1，可能是次优的。Knuth 本人给 64 位找的乘数最多只有 4 个连续的 0。我曾为不同位宽的 LCG 挖掘过乘数，用 diehard 测试检验，常常能通过。这个话题有大量学术工作可读。
strainer查看英文原文
The Golden Ratio is proposed as a special multiplier for what is otherwise known as 'linear congruential' psuedorandom number generation. I'm not clear on whether the non-repetitive property of the ratio will benefit its performance at all. This decimal is computed for 2^64 /1.618... 11400714819323198486 -it looks like this in binary: 1001111000110111011110011011100101111111010010100111110000010101 The runs of 7 ones, 5 zeros and 5 ones could be sub-optimal. [1] Donald Knuth himself discovered this one for 64bits: 101100001010001111101000010110101001100100101010111111100101101 It contains a run of 7 ones, and 5, but maximum zeros in a row is 4. I did once mine multipliers for LCGs of different bitlengths by comparing quickly measured ratios in their output to those precomputed from good psuedorandom sequences (average deviation etc) Then having found numbers which achieved the basic signature of random data, they were tested with Marsaglia's old 'diehard' battery of tests - and often passed. Here is a multiplier discovered for a 32bit LCG 110010011101110100001011 I had a list of them I meant to examine here, but have lost it :( Anyway, there is plenty of academic work to read on this subject: 1 - https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选