按年被提到
20152015 · 2 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1503.03465 · cs.DS

Faster 64-bit universal hashing using carry-less multiplications

用无进位乘法实现更快的 64 位通用哈希
Daniel Lemire, Owen Kaser · 2015

基于 CLMUL 指令的几乎通用哈希族 CLHASH,比 CityHash 更快

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 3 人首次 2015-10-27 · 最近 2016-12-04
3不同的人
4活跃月份
4讨论串
26被引(OpenAlex)

Intel 和 AMD 的 x64 处理器支持无进位乘法(CLMUL)指令集,作者用它实现了一个几乎通用的 64 位哈希族 CLHASH。与可能是 x64 上最快的几乎通用哈希族 VHASH 相比,CLHASH 至少快 60%;与以速度见长的 Google CityHash 相比,在大于 64 字节的输入上快 40%,其余情况同样快。

HN 为什么提它

HN 上的人把它推荐为要在现代处理器上实现高性能哈希时更好的起点,也引用其中 SMHasher 质量结果和 CLHash 的规格。

方法难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1哈希函数与通用哈希(universal hashing)
2有限域 GF(2) 上的运算
3x86 SIMD 与 CLMUL 指令
4性能评测与 SMHasher

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐nkurz · 2016-12

“But if you are hoping to implement high performance solution for modern processors, the 2015 Lemire and Kaser paper is probably a better starting point.”

推荐 Lemire 和 Kaser 2015 年论文作为高性能实现的更好起点
Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions (2013)原评论 ↗
引用twotwotwo · 2015-10

“The paper goes into that section 6.1”

引其 6.1 节,CLHash 的 SMHasher 质量结果
Crazily fast hashing with carry-less multiplications原评论 ↗
引用jbapple · 2016-03

“Faster 64-bit universal hashing using carry-less multiplications”

贴出该论文,CLHASH 为 64 位输出、近通用、每字节 0.16 周期
HighwayHash: Strong hashing at 0.3 clock cycles per byte原评论 ↗
被提交为 story · 1 次