CRC-32哈希的唯一性足以唯一标识包含文件名的字符串吗？

Question

CRC-32哈希的唯一性足以唯一标识包含文件名的字符串吗？

hashcrc32hash-code-uniqueness

7

我有一些文件名的列表，它们被拼接成字符串，并且我想通过唯一的校验和来识别每个字符串。

这些字符串的大小最小为100字节，最大为4000字节，平均为1000字节。总字符串数可能是任意的，但更有可能在约10000的范围内。

CRC-32适用于此目的吗？

例如，我需要以下每个字符串具有不同的定长（最好是短的）校验和：

"/some/path/to/something/some/other/path"
"/some/path/to/something/another/path"
"/some/path"
...
# these strings can get __very__ long (very long strings are the norm)

CRC-32哈希算法的唯一性是否随输入长度增加而增加？

在此情况下，有没有更好的校验和选择？

- MCH

如果您已经有一个唯一的校验和，那么问题是什么？ - Ryan Vincent

问题在于缩短这些字符串，重新计算它们，重新计算校验和，然后查看校验和是否已经被计算过。我想确保crc-32适用于此，因为我不太了解哈希函数，并希望最小化碰撞概率。 - MCH

1

你预计总共会有多少条目？猜测一下？1000，10000（1e5），一百万（1e6），还是更多？ - Ryan Vincent

1

你介意在你的问题评论中添加数值吗？我认为这将有助于其他人回答你的问题，因为他们知道“问题的规模”。感谢提供信息 - 这对我们很有帮助。 - Ryan Vincent

2

在我看来，我会为您的应用程序使用“md5”哈希。它快速且不太可能产生冲突。但请注意，它不能用于任何与安全相关的事务。在我看来，它更适合用于快速查找文件名。 - Ryan Vincent

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Adler · Accepted Answer

不。

除非您的文件名都是四个字符或更少，否则不能保证CRC唯一。对于10000个名称，至少有两个名称具有相同CRC的概率约为1%。

这对于任何32位哈希值都是正确的。

将唯一代码分配给每个名称的最佳方法是为第一个名称从零开始计数，并且为每个名称递增，将计数作为该名称的代码分配。但是，这样做将无法帮助您仅凭名称计算代码。

您可以使用哈希，例如CRC或其他哈希，但您需要处理冲突。文献中有几种常见的方法。您将保留具有分配名称的哈希列表，如果出现冲突，则可以仅递增哈希，直到找到未使用的哈希并分配该哈希。然后，在查找名称时，您从计算的哈希开始进行线性搜索，直到找到名称或未使用的插槽。

至于哈希，我建议使用XXH64。它是一种非常快的64位哈希。对于此应用程序，您不需要加密哈希，这将使速度过慢。