我正在使用 SHA-1 来检测程序处理文件中的重复项。它不需要是加密强的，并且可能是可逆的。我找到了这个快速哈希函数列表https://code.google.com/p/xxhash/
如果我想要在 SHA-1 附近的随机数据上获得更快的函数和冲突，我应该选择什么？
也许 128 位散列足以用于文件重复数据删除？（与 160 位 sha-1 相比）
在我的程序中，哈希是根据 0 - 512 KB 的块计算的。
问问题
11248 次
7 回答
9
碰撞罕见：FNV-1、FNV-1a、DJB2、DJB2a、SDBM 和 MurmurHash
我不知道 xxHash，但它看起来也很有希望。
MurmurHash 非常快，版本 3 支持 128 位长度，我会选择这个。（在 Java 和 Scala 中实现。）
于 2015-04-08T13:48:36.770 回答
4
由于在您的情况下哈希算法的唯一相关属性是碰撞概率，因此您应该估计它并选择满足您要求的最快算法。
如果我们假设您的算法具有绝对一致性，则使用具有d个可能值的哈希的n 个文件之间发生哈希冲突的概率将为：
例如，如果您需要在一百万个文件中低于百万分之一的冲突概率，您将需要有超过 5*10^17 个不同的哈希值，这意味着您的哈希需要至少有 59 位。让我们四舍五入到 64 以说明可能的不均匀性。
所以我想说任何体面的 64 位哈希对你来说应该足够了。更长的哈希将进一步降低冲突概率，代价是计算量更大，哈希存储量增加。CRC32 等较短的缓存将需要您编写一些显式的冲突处理代码。
于 2015-04-14T13:01:40.277 回答
3
谷歌开发并使用（我认为）FarmHash 用于性能关键的哈希。从项目页面：
FarmHash 是 CityHash 的继承者，包括许多相同的技巧和技术，其中一些取自 Austin Appleby 的 MurmurHash。
...
在具有所有必要机器指令的 CPU 上，大约六种不同的哈希函数可以为 FarmHash 的阵容做出贡献。在某些情况下，通过使用现在普遍可用的更新指令，我们在 CityHash 上取得了显着的性能提升。但是，我们也通过其他方式提高了一些速度，因此绝大多数使用 CityHash 的程序在切换到 FarmHash 时应该至少会有所提升。
（CityHash 已经是 Google 的性能优化哈希函数系列。）
它是在一年前发布的，当时几乎可以肯定它是最先进的，至少在已发布的算法中是这样。（否则谷歌会使用更好的东西。）很有可能它仍然是最好的选择。
于 2015-04-09T10:11:24.633 回答
3
事实：
- 良好的散列函数，特别是加密函数（如 SHA-1），需要相当多的 CPU 时间，因为它们必须遵守许多在这种情况下对您不会非常有用的属性；
- 任何散列函数只会给你一个确定性：如果两个文件的散列值不同，则文件肯定不同。但是，如果它们的哈希值相等，则文件也可能相等，但是确定这种“相等”是否不仅仅是哈希冲突的唯一方法是回退到两者的二进制比较文件。
结论：
在你的情况下，我会尝试一个更快的算法，比如 CRC32，它几乎具有你需要的所有属性，并且能够处理超过 99.9% 的情况，并且只能采用较慢的比较方法（比如二进制比较）以排除误报。在绝大多数比较中更快可能会弥补没有“令人敬畏”的均匀性（可能会产生更多的碰撞）。
于 2015-04-11T05:16:33.330 回答
3
128 位确实足以检测不同的文件或块。碰撞的风险是微乎其微的，至少只要没有故意碰撞的企图。
如果您要跟踪的文件或块的数量保持“足够小”（即不超过几百万个），64 位也可以证明足够好。
一旦确定了散列的大小，您需要一个具有一些非常好的分布属性的散列，例如在您的链接中以 Q.Score=10 列出的那些。
于 2015-04-11T08:33:53.573 回答
1
这有点取决于您将在一次迭代中计算多少哈希。例如，64 位散列在计算 600 万个散列时达到 1000000 分之一的冲突概率。
参考：哈希碰撞概率
于 2015-04-14T13:45:21.413 回答
1
查看MurmurHash2_160。它是对 MurmurHash2 的修改，可产生 160 位输出。
它并行计算 MurmurHash2 的 5 个独特结果并将它们彻底混合。基于摘要大小，冲突概率等同于 SHA-1。
它仍然很快，但 MurmurHash3_128、SpookyHash128 和 MetroHash128 可能更快，尽管碰撞概率更高（但仍然非常不可能）。还有 CityHash256 产生 256 位输出，它也应该比 SHA-1 更快。
于 2018-04-16T15:31:11.547 回答