5

我已经对连接到字符串的文件名列表进行了排序，并希望通过唯一的校验和来识别每个这样的字符串。

这些字符串的大小最小为 100 字节，最大为 4000 字节，平均为 1000 字节。字符串的总数可以是任何东西，但更有可能在 ca 的范围内。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 哈希的唯一性是否会随着输入长度的增加而增加？

为此目的是否有更好的校验和选择？

4

1 回答 1

13

不。

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

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

为每个名称分配唯一代码的最佳方法是简单地从零开始为第一个名称创建一个计数器，并为每个名称递增，将计数器分配为该名称的代码。但是，这不会帮助您计算仅给出名称的代码。

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

至于哈希，我会推荐XXH64。这是一个非常快的 64 位散列。您不需要此应用程序的加密哈希，这会不必要地慢。

于 2016-04-14T19:47:16.763 回答