能否使用CRC32C作为基础构建一个“好”的哈希函数？

Question

考虑到 SSE 4.2 （Intel Core i7 和 i5 部件）包含一个 CRC32 指令，因此研究是否可以构建更快的通用哈希函数似乎是合理的。根据这里的说明，CRC32 中仅有 16 位均匀分布。那么要克服这个问题，需要应用什么其他变换呢？ 更新 怎么样？只有 16 位适合作为哈希值。太好了，如果您的表小于等于 65535，那就很棒了。如果不是，请将 CRC 值通过 Nehalem POPCNT（人口普查）指令运行以获取设置的位数。然后将其用作表数组中的索引。如果您的表少于 1 亿条目，则此方法有效。我打赌这比性能最佳的哈希函数更便宜/更快。现在GCC 4.5具有 CRC32 内置函数，测试应该很容易...如果我有大量空闲时间来进行工作的话。

David

- DavidD

Answer 1

更新，2014年8月
在最近的一条评论中，由于Arnaud Bouchez和其他回答和评论的影响，我承认原始答案需要修改或至少有资格。我保留了原始答案作为参考。

首先，也许最重要的是，对问题的公正回答取决于哈希代码的预期用途：使用“好”[哈希函数]的意义是什么？哈希将在何处/如何使用？（例如，它是用于散列相对较短的输入密钥吗？用于索引/查找目的，生成消息摘要或其他用途？所需哈希代码本身有多长，全部32位[CRC32或其派生物]，更多位，更少...等等？
OP的问题要求“更快的通用哈希函数”，因此重点是速度（一些不太CPU密集的东西和/或可以利用各种性质的并行处理）。我们可能会注意到，在哈希应用程序中，哈希代码本身的计算时间通常只是问题的一部分（例如，如果哈希代码的大小或其固有特性导致许多冲突，这需要额外的周期来处理）。此外，“通用”要求留下了许多关于可能用途的问题。

考虑到这一点，一个简短而更好的答案可能是：

是的，较新的英特尔处理器上的CRC32C硬件实现可以用于构建更快的哈希代码；但是请注意，由于碰撞频率和需要使用更长的代码，根据哈希的具体实现和应用程序，总体结果可能不太理想。此外，对于哈希的加密用途，应该仔细审查，因为CRC32算法本身在这方面非常薄弱。

原始答案引用了Bret Mulvey关于评估哈希函数的文章，并如Mdlg的答案所指出，这篇文章的结论在CRC32方面是错误的，因为它所基于的CRC32实现有缺陷/错误。尽管在CRC32方面存在这个重大错误，但该文章提供了有关哈希算法属性的有用指导。该文章的URL已失效；我在archive.today上找到了它，但我不知道作者是否将其放在另一个位置并且是否更新了它。

其他答案引用了CityHash 1.0作为使用CRC32C的哈希库的例子。显然，这是在一些长（超过32位）哈希码的上下文中使用的，但不适用于CityHash32()函数本身。此外，与生成哈希码的所有移位、洗牌和其他操作相比，City Hash函数使用CRC32的相对较少。（这并非针对CityHash的批评，因为我没有实际经验。从对源代码的简要审查中可以得出结论，CityHash函数产生良好的分布式代码，但与各种其他哈希函数相比，并没有显著提高速度。）

最后，您还可以在SO上的准重复问题中找到有关此问题的见解。

---

原始答案和编辑（2010年4月）：

先验地，这听起来像一个糟糕的主意！

CRC32并非为哈希目的而设计，其分布很可能不均匀，因此使其成为相对较差的哈希码。此外，其“混淆”能力相对较弱，使其成为单向哈希的非常不良选择，例如在加密应用中使用。

[BRB：我正在寻找相关的在线参考文献...]

谷歌搜索关键词[CRC32 distribution]的第一条结果似乎证实了这一点：
评估 CRC32 用于哈希表

编辑：上面引用的页面，实际上提供了关于查找哈希函数的良好基础。
快速阅读这篇文章，确认了总体上CRC32通常不应该用作哈希函数的结论，然而，根据哈希的特定目的，可能可以将CRC32的某些部分用作哈希码。

例如，CRC32代码的低（或高，取决于实现）16位具有相对均匀的分布，并且，只要不关心哈希码的加密属性（例如类似键产生非常相似的代码），就可以构建使用两个CRC32代码的较低[或较高] 16位的连接来生成哈希码，这些代码是使用原始键的两半（或任何分割）产生的。
需要运行测试以查看内置CRC32指令的效率与其他哈希函数相比是否足够，以使调用指令两次并拼接代码等开销不会导致整体功能变慢。

- mjv

---

@rsking。不完全是这样。减少可能碰撞的数量是CRC设计的次要目标；主要目标是在特定预期密钥分布的情况下最大化其错误检测性能。对于纯随机密钥，这两个目标是完全兼容的，但是通常会选择特定通道的CRC，无论是在其典型内容方面还是在其最常见的错误模式方面。这特别适用于CRC32和K Brayer和J Hammond在1975年的论文中明确提到了这一点。此外... - mjv

CRC32 不均匀分布的事实可以通过多种经验测试来确定，例如答案中提到的测试。这种不良（全局）分布并不是设计缺陷，而是确认重点在于限制在相似长度的消息发送到同一个有干扰声道的情况下的碰撞，而不是针对提交到随机噪声的任意消息。因此，CRC 并不一定适合用作通用哈希函数。 - mjv

引用的文章作为参考使用了错误的crc32实现-请参见下面的Mdlg答案。因此，这篇文章不是“寻找哈希函数的好基础”。我希望看到这个答案被更新。根据我的实验，crc32非常适合作为哈希函数的候选。 - Arnaud Bouchez

@ArnaudBouchez，感谢您督促我改进答案。顺便说一句，我觉得有必要进行这个长时间的编辑，尽管这可能看起来像是我不想承认自己错了。我真心希望我的原始答案是完全错误的（这样维基百科就可以通过仅删除它或在其顶部添加几个指向为什么它是错误的和更好的答案在哪里找到的单词，而不是这个漫长的讨论）。 - mjv

@mjv 感谢您的更新！现在我们可以开始讨论了。 ;) 就我所知，OP 明确要求使用哈希函数来进行哈希表操作（请参阅“更新”）：因此，您可以简化您的答案 - 不需要讨论其他用途，比如消息摘要。32 位精度对于哈希表来说已经足够了（除非您的哈希表将有 2^32 个插槽，即在 x64 中使用 32 GB 的 RAM - 这是不可行的）。因此，在这种情况下，“crc32c”听起来像是通用哈希函数的赢家。这就是您的答案现在所陈述的内容！太好了！ :) - Arnaud Bouchez

Answer 2

其他答案提到的文章基于有缺陷的crc32代码得出了错误的结论。 谷歌的排名算法目前不是基于科学准确性而排名的。

与参考文章“评估哈希表的CRC32”的结论相反，CRC32和CRC32C适用于哈希表使用。 作者的示例代码在crc32表生成方面存在错误。修复crc32表后，使用相同的方法得到令人满意的结果。此外，CRC32指令的速度使其成为许多场景下的最佳选择。使用CRC32指令的代码峰值速度比最佳软件实现快16倍。（请注意，CRC32与英特尔指令实现的CRC32C不完全相同）。

CRC32显然不适用于加密用途。（32位可以被暴力破解）。

- Mdlg

---

值得一提的是，引用的文章错误地实现了crc32！在实践中，我们发现，在处理UTF-8文本时，crc32是速度和冲突方面的最佳折衷（比如Kernighan＆Ritchie，BobJenkins，FNV1a更好）。而且最新的SSE4.2 CPU确实有一个硬编码的crc32c指令，它在性能方面优于其他所有东西。请参见http://blog.synopse.info/post/2014/05/25/New-crc32c%28%29-function-using-optimized-asm-and-SSE-4.2-instruction和http://www.delphitools.info/2014/08/25/string-hashing-shootout/comment-page-1/#comment-3423。 - Arnaud Bouchez

不仅可以轻松地进行暴力破解，而且还可以通过分析方法来解决。 - Jasen

Answer 3

是的。 CityHash 1.0.1 包含了一些使用 CRC32 指令的新“好哈希函数”。

- user730496

Answer 4

为了加密目的，CRC32是一个糟糕的基础，因为它是线性的（在向量空间GF（2）^32上），很难进行纠正。它可能适用于非加密目的。

然而，最近的英特尔核心具有AES-NI指令，基本上在两个时钟周期内执行1/10的AES块加密。它们可用于最新的i5和i7处理器（请参阅维基百科页面以获取一些详细信息）。这看起来是构建加密哈希函数的好开始（对于加密的哈希函数也将对其他任何事情都很好）。

实际上，至少有一个SHA-3“第二轮”候选者（ECHO哈希函数）是基于AES元素构建的，因此AES-NI操作码提供了非常大的性能提升。（不幸的是，在没有AES-NI指令的情况下，ECHO性能有些糟糕。）

- Thomas Pornin

Answer 5

只要您不需要加密哈希，它可能会起作用。

- Joshua