在SHA-1附近具有冲突可能性的快速哈希函数

Question

我正在使用SHA-1来检测程序处理文件中的重复项.它不需要加密强大并且可以是可逆的.我找到了这个快速哈希函数列表https://code.google.com/p/xxhash/

如果我想在SHA-1附近的随机数据上获得更快的功能和冲突,我该选择什么？

也许128位哈希足以用于文件重复数据删除？(vs 160 bit sha-1)

在我的程序中,哈希是在0到512 KB的块上计算的.

Answer 1

也许这会对你有所帮助:https: //softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed

稀有碰撞:FNV-1,FNV-1a,DJB2,DJB2a,SDBM和MurmurHash

我不知道xxHash,但看起来也很有希望.

MurmurHash非常快,版本3支持128位长度,我会选择这个.(在Java和Scala中实现.)

Answer 2

由于在您的情况下，哈希算法的唯一相关属性是冲突概率，因此您应该估计它并选择满足您要求的最快算法。

如果我们假设您的算法具有绝对一致性，则使用具有d 个可能值的哈希值的n 个文件之间发生哈希冲突的概率将是：

例如，如果您需要一百万个文件中的冲突概率低于百万分之一，则需要有超过 5*10^17 个不同的哈希值，这意味着您的哈希值需要至少有 59 位。让我们四舍五入到 64，以考虑可能出现的较差均匀性。

所以我想说任何像样的 64 位哈希应该足以满足您的需求。较长的哈希值将进一步降低冲突概率，但代价是计算量更大和哈希存储量增加。像 CRC32 这样的较短缓存将要求您编写一些显式的冲突处理代码。