我正在编写一个磁盘缓存，其中文件名是键。密钥可以长于最大文件名长度，因此需要对其进行哈希处理。有哪些碰撞概率极低的快速哈希函数（以便我可以忽略它）？
基本上，我正在寻找一种没有安全要求的更快的 MD5 替代方案。
（平台 = Android，语言 = Java。）
问问题
3068 次
2 回答
6
如果您的哈希是均匀分布的，那么您可以根据您希望在冲突之前处理的大约文件数来计算所需的哈希大小（以位为单位）。基本上，由于生日悖论，它是比特数的两倍。
因此，例如，如果您对一百万个文件后的冲突感到满意，那么您需要一个大约 40 位 log (2 * log2(1e6)) 的 has。
相反，如果哈希是 N 位，那么它适用于 2^(N/2) 个没有冲突（或多或少）的文件。
有很多快速哈希。例如，xxhash是 64 位哈希，因此适用于大约 4,000,000,000 个文件。 谷歌的快速哈希是另一个。
如果您想要超过 64 位（在发生冲突之前超过约 40 亿个文件），那么您可以使用具有更大输出的散列或将两个 64 位散列连接在一起（一个来自原始文件的散列和一个以某种方式修改的散列（例如以空格为前缀））。
于 2013-09-08T22:00:23.467 回答
0
google guava 库有不同的快速哈希实现：
于 2015-04-12T13:51:35.280 回答