我正在尝试实施一个计数最小草图 http://en.wikipedia.org/wiki/Count-Min_sketchScala中的算法，所以我需要生成k个成对独立的哈希函数。
这是一个比我以前编写过的任何东西都低的级别，除了算法类之外，我对哈希函数了解不多，所以我的问题是：如何生成这 k 个成对独立的哈希函数？
我应该使用 MD5 或 MurmurHash 等哈希函数吗？我是否只生成以下形式的 k 个哈希函数f(x) = ax + b (mod p)，其中 p 是素数，a 和 b 是随机整数？ （即通用哈希家族 http://en.wikipedia.org/wiki/Universal_hashing每个人都在算法中学习 101)
我更注重简单性而不是原始速度（例如，如果实现起来更简单，我会以慢 5 倍的速度运行）。
Scala已经有MurmurHash已实施（这是scala.util.MurmurHash）。它非常快并且非常擅长分配值。加密哈希是多余的——你只会花费比你需要的时间长几十或几百倍的时间。就选k从不同的种子开始，因为它的质量几乎是加密的，所以你会得到k很大程度上独立的哈希码。 （在 2.10 中，您可能应该改用scala.util.hashing.MurmurHash3;用法相当不同，但你仍然可以通过混合来做同样的事情。）
如果您只需要将近值映射到随机的远值，这将起作用；如果你想避免冲突（即，如果 A 和 B 使用哈希 1 发生冲突，那么它们可能不会使用哈希 2 发生冲突），那么你至少需要再执行一步，而不是对整个对象进行哈希处理，而是对它的子组件进行哈希处理，这样哈希值有可能以不同的方式开始。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
