我正在编写一个以文件名为键的磁盘缓存。 key 可以长于最大文件名长度，因此需要对其进行哈希处理。有哪些碰撞概率极低的快速哈希函数(以便我可以忽略它)？
基本上，我正在寻找一种没有安全要求的更快的 MD5 替代方案。
(平台 = Android，语言 = Java。)
最佳答案
如果您的散列是均匀分布的，那么您可以根据您希望在冲突前处理的文件的大约数量来计算您需要的散列大小(以位为单位)。基本上，由于生日悖论，它是位数的两倍。
因此，例如，如果您对一百万个文件后的碰撞感到满意，那么您需要一个大约 40 位日志 (2 * log2(1e6)) 的 has。
相反，如果哈希是 N 位，那么它适用于 2^(N/2) 个文件而不会发生冲突(或多或少)。
有很多快速哈希。例如，xxhash是 64 位哈希，因此适用于大约 4,000,000,000 个文件。 google's fast-hash是另一个。
如果您想要超过 64 位(冲突前超过 40 亿个文件)，那么您可以使用具有更大输出的散列或将两个 64 位散列连接在一起(一个来自原始文件的散列和一个修改后的散列)某种方式(例如以空格为前缀))。
关于java - 具有唯一哈希值的快速哈希函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18686945/