算法与理论计算机2014arxiv.org编辑精选
一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
进阶 · 约 25 分钟读完前置知识：一致性哈希、哈希函数、基础概率
导读
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。评论提到它在标准误差、内存占用和执行速度上优于对照方案，再平衡成本相当；Google 明确表示不为此申请专利，并愿将算法贡献给社区。
HN 关注点：既因为作者 Eric Veach 的传奇背景和 Google 的不专利声明，也因为哈希算法依赖 double 浮点运算带来的可重复性与可移植性争议。
后来怎么样
提出的 Jump Consistent Hash 后来被 Google Guava 采用，并成为低内存、快速一致哈希的常见实现方案之一。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 2
补充作者 Eric Veach 背景显赫，新论文因而格外引人关注。
哇，这立刻吸引了我的注意，因为作者里有 Eric Veach。我已经很久很久没看到他的（相对）新论文了。背景：Eric Veach 在计算机图形学界地位很高，他的博士论文为现代基于物理的渲染打下了大量基础；之后他去 Pixar 做了大量 Renderman 相关工作，并因此获得奥斯卡奖；2000 年代初又离开 Pixar 去 Google，主导开发了 AdWords。总之他的职业生涯相当辉煌，看到他的新论文总是很有意思。
ykl查看英文原文
Woah, this jumps out at me immediately since Eric Veach's name is on it. I haven't seen a (relatively) new Eric Veach paper in a long long time. Some background: Eric Veach is huge in the computer graphics world for laying a ton of the foundations of modern physically based rendering in his PhD thesis [1]. He then went on to work for Pixar and did a ton of work on Renderman (for which he recently got an Academy Award), and then in the early 2000ish left Pixar to go work for Google, where he was the lead on developing AdWords [2]. In short, he's had quite a career, and seeing a new paper from him is always interesting. [1] https://graphics.stanford.edu/papers/veach_thesis/ [2] http://www.bloomberg.com/bw/stories/2006-03-05/the-secret-to-googles-success
支持算法在误差、内存、速度和再平衡成本上全面占优，且 Google 承诺不申请专利。
更小的标准误差、显著更少的内存、更快的执行、相当的再平衡成本……还有什么可挑剔的？感谢 Google：Google 没有为该算法申请专利保护，而且截至本文写作时也没有此计划，而是希望把它贡献给社区。
dbenhur查看英文原文
Smaller standard error, significantly less memory, faster execution, equivalent rebalance cost... what's not to like? Thanks, Google: > Google has not applied for patent protection for this algorithm, and, as of this writing, has no plans to. Rather, it wishes to contribute this algorithm to the community.
补充论文其实是 Guava 中已使用两年半的算法的事后说明。
论文里似乎没有提到，但这描述的其实是 Google Guava 库中的“consistent hashing”算法。我觉得有点好笑：他们创造并发布了一个看似新颖的哈希方法，却等了 2.5 年才解释它如何工作。
teraflop查看英文原文
It doesn't seem to be mentioned anywhere in the paper, but this is a description of the "consistent hashing" algorithm in Google's Guava library: http://docs.guava-libraries.googlecode.com/git/javadoc/src-html/com/google/common/hash/Hashing.html#line.323 I find it kind of funny that they created and released an apparently novel hashing method, and then waited 2.5 years to actually explain how it works.
质疑哈希依赖 double 浮点运算，跨编译优化和架构可能不可重复，可靠性存疑。
在哈希算法里使用 double 在我看来非常危险。多年来我一直遇到不同优化级别下浮点代码给出不同结果的问题，因为不同寄存器内部位宽不同、浮点寄存器可能有不同内部精度等。这个哈希函数能可信地产生可重复结果吗？
CJefferson查看英文原文
Using doubles in a hash algorithm seems (to me) very dangerous. For years I have had problems with different optimisation levels providing different results for floating point code, as different registers have different internal sizes, FP registers can have different internal precision, etc. Can this hash function be trusted to produce repeatable results?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2014Hacker News 讨论帖121 分 · 22 评
- 2015Hacker News 讨论帖129 分 · 26 评
- 2015Hacker News 讨论帖31 分 · 4 评
- 2019Hacker News 讨论帖46 分 · 5 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选近线性时间内的最大流与最小费用流
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
给出了最大流与最小费用流的近线性时间精确算法，是理论计算机科学的重要突破。
算法与理论计算机2022 · 230 分 · 40 评 · 引用 8专业 · 约 120 分钟编辑精选