算法与计算机科学mollyrocket.com
Meow Hash (2018)
Meow Hash (2018)
2018 — 2021，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
Meow Hash 是 Casey Muratori（mollyrocket）在 2018 年发布的非加密哈希函数，利用 AES-NI 指令对大块数据（如游戏资产包）做极快速的校验与去重哈希，输出 128 位。作者称其在大数据量场景下远快于 SHA-1 等传统方案，且实践中几乎不产生碰撞。
为什么经久不衰：它展示了用硬件 AES 指令做非加密哈希的思路，虽然后来被 XXH3 等超越并发现碰撞，但作为大数据哈希性能设计的经典案例仍值得了解。
HN 评论精选
Meow Hash 速度快但质量一般，XXH3 是更成熟的替代方案
有人对 Meow Hash 做了详细密码分析（见链接）。它并不是质量很高的哈希函数（可参考 SMHasher 基准测试），但确实很快。一个更好的替代品是 XXH3，它在实际中使用的广泛程度远超 Meow Hash。
anonova查看英文原文
A detailed analysis of Meow Hash: https://peter.website/meow-hash-cryptanalysis It's not the highest of quality hash functions (see the SMHasher benchmarks), but it is fast. A great alternative is XXH3 (https://cyan4973.github.io/xxHash/), which has seen far more usage in practice.
实测显示 Meow 对长输入快约 2 倍，但短输入性能较差
补上实际基准测试（老款带 AES-NI 的 Xeon E5-2670）：对大于 4KB 的数据，Meow 比其他哈希快约 2 倍，直到超出缓存、受内存带宽限制为止。对比：xxHash64 约 13GB/s，Metrohash128 约 13GB/s，Metrohash128_crc 约 18GB/s。Meow 在 64-96 字节以下才突破 1GB/s，而其他哈希 8 字节就能达到。所以它长输入快（得益于 AES 混合和并行流水线），短输入慢（结尾混合存在依赖）。
DrJosiah查看英文原文
Late to the party, some actual benchmarks using an older CPU with AES-NI: Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz bugs : cpu_meltdown spectre_v1 spectre_v2 spec_store_bypass l1tf Kernel 4.18.14 GCC 7.3.0 Short version, it's ~2x as fast as anything else on my machine for data > 4k, maybe down to 1k, all the way up to > cache (where various other algorithms also max out memory bandwidth). Other non-cryptographic hashes (for comparison) on my local machine: xxHash64 -> ~13G/s, Metrohash128 -> ~13G/s, Metrohash128_crc -> ~18G/s, t1ha_crc -> ~17.5G/s, etc., but Meow doesn't break the 1G/s barrier until 64-96 bytes (the others mentioned reach that speed at 8 bytes). So yeah, faster for longer keys due to the fast aes mixing + parallel pipeline usage, but slower for shorter keys due to the final mixing dependency at the end. Using a hacked-up version of Smhasher for wider range of hashing sizes (cache on this CPU is 20 megs): --- Testing Meow1_64 "parallel aes internals" [[[ Speed Tests ]]] Bulk speed test - 67108864-byte keys Average - 4.556 bytes/cycle - 14337.09 MiB/sec @ 3 ghz Bulk speed test - 16777216-byte keys Average - 7.882 bytes/cycle - 24805.52 MiB/sec @ 3 ghz Bulk speed test - 4194304-byte keys Average - 9.813 bytes/cycle - 30884.30 MiB/sec @ 3 ghz Bulk speed test - 1048576-byte keys Average - 9.657 bytes/cycle - 30390.48 MiB/sec @ 3 ghz Bulk speed test - 262144-byte keys Average - 10.642 bytes/cycle - 33490.19 MiB/sec @ 3 ghz Bulk speed test - 65536-byte keys Average - 11.871 bytes/cycle - 37360.76 MiB/sec @ 3 ghz Bulk speed test - 16384-byte keys Average - 11.336 bytes/cycle - 35675.98 MiB/sec @ 3 ghz Bulk speed test - 4096-byte keys Average - 8.241 bytes/cycle - 25936.55 MiB/sec @ 3 ghz Bulk speed test - 1024-byte keys Average - 4.056 bytes/cycle - 12765.26 MiB/sec @ 3 ghz
Meow Hash 已被发现实际碰撞
几个月前有人报告了一个碰撞案例（见 GitHub issue #80）。
arduinomancer查看英文原文
A collision was reported a couple months ago https://github.com/cmuratori/meow_hash/issues/80
变更检测不必哈希全部字节，哈希局部区域加长度即可
你们之前用 SHA-1 慢，是因为对每个字节都做哈希，这没必要。哈希的作用是：不同则确认不同，相同则可能相同也可能不同。为此不必哈希全部内容，只需哈希可能不同的区域。比如哈希（长度 + 首部 1KB + 尾部 1KB）就够用了；去重场景下 32 位 CRC 可能就足够高效，反正无论用什么哈希都得验证碰撞。
kazinator查看英文原文
> Because we have to process hundreds of gigabytes of art assets to build game packages, we wanted a fast, non-cryptographic hash for use in change detection and deduplication. We had been using a cryptographic hash (SHA-1), but it was unnecessarily slowing things down. That's because you were doing a potentially silly thing: hashing every byte. What does a hash tell you? If two hashes are different, it confirms that the objects are different. If two hashes are the same, they could be the same object or they could be different. For that purpose, you don't have to hash everything: just hash the areas where objects are likely to differ. If two 15 gigabyte files are likely to have differences in their first kilobyte, then hashing just first kilobyte (negligibly fast) will work just as well as hashing 15 gigabytes. If two files are of different length, then they are not the same. How about: hash(<length> + <first kilobyte> + <last kilobyte>) For deduplication, a 32 bit CRC could probably be reasonably efficient. No matter what hash you use, you have to verify the collisions. If CRC32 is enough to make false positives rare over your type of data set, it's good enough.
历次讨论
同类还值得读
位运算技巧集
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编辑精选