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

Question

我已经将连接到字符串的文件名列表排序,并希望通过唯一的校验和来标识每个这样的字符串.

这些字符串的大小至少为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哈希的唯一性是否因输入长度而增加？

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

Answer 1

没有.

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

对于任何32位散列值都是如此.

为每个名称分配唯一代码的最佳方法是简单地为第一个名称启动一个零计数器,并为每个名称递增,将计数器指定为该名称的代码.但是,这不会帮助您计算仅给出名称的代码.

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

至于哈希,我会推荐XXH64.它是一个非常快速的64位哈希.您不需要为此应用程序使用加密哈希,这会非常慢.