hash - uris 的高效哈希函数

Question

我正在寻找一个哈希函数来为字符串构建一个（全局）固定大小的 id，其中大多数是 URI。

它应该是：

• 快速地
• 碰撞几率低
• ~ 64 位
• 如果可能的话，利用uri的结构？

http://murmurhash.googlepages.com/会是一个不错的选择还是有什么更适合的？

Answer 1

尝试MD4。就密码学而言，它是“损坏的”，但由于您没有任何安全问题（您想要一个 64 位输出大小，它太小而无法产生任何体面的碰撞安全性），这不应该是问题。MD4 产生一个 128 位的值，您只需将其截断为您希望的大小。

密码散列函数旨在适应建立冲突的显式尝试。可以想象，人们可以通过放宽该条件来构建更快的函数（与确定的攻击者相比，击败随机碰撞更容易）。有一些这样的函数，例如 MurmurHash。但是，可能需要非常具体的设置才能真正注意到速度差异。使用我的家用 PC（2.4 GHz Core2），我可以使用单个 CPU 内核（我有四个内核）使用 MD4 每秒散列大约 1000 万个短字符串。为了让 MurmurHash 以不可忽略的方式比 MD4 更快，它必须在每秒涉及至少一百万次哈希调用的上下文中使用。这种情况并不经常发生……

Answer 2

我会等待 MurmurHash3 完成，然后使用它。128 位版本应该为您提供针对生日悖论的足够碰撞保护。