10

我正在尝试在 Scala 中实现Count-Min Sketch算法，因此我需要生成 k 成对独立哈希函数。

这是一个比我以前编程过的任何东西都低的级别，而且我对哈希函数了解不多，除了算法类，所以我的问题是：我如何生成这些 k 成对独立的哈希函数？

我应该使用像 MD5 或 MurmurHash 这样的哈希函数吗？我是否只生成 k 形式的散列函数f(x) = ax + b (mod p)，其中 p 是素数，a 和 b 是随机整数？（即，每个人都在算法 101 中学习的通用散列系列）

我正在寻找比原始速度更简单的东西（例如，如果实现起来更简单，我会慢 5 倍）。

4

2 回答 2

5

Scala 已经MurmurHash实现了（它的scala.util.MurmurHash）。它非常快速且非常擅长分配价值。加密哈希是多余的——你只需要比你需要的时间长几十或几百倍。只需选择k不同的种子开始，由于它的质量几乎是加密的，您将获得k很大程度上独立的哈希码。（在 2.10 中，您可能应该切换到 using scala.util.hashing.MurmurHash3；用法有很大不同，但您仍然可以通过混合来做同样的事情。）

如果您只需要将近值映射到随机远值，这将起作用；如果您想避免冲突（即，如果 A 和 B 使用哈希 1 发生冲突，它们可能不会也使用哈希 2 发生冲突），那么您至少需要再走一步，而不是对整个对象进行哈希处理，而是对它的子组件进行哈希处理哈希有机会以不同的方式开始。

于 2012-08-25T16:38:57.290 回答
2

可能最简单的方法是采用一些加密哈希函数并用不同的字节序列“播种”它。对于大多数实际目的，结果应该是独立的，因为这是加密散列函数应该具有的关键属性之一（如果替换消息的任何部分，散列应该完全不同）。

我会做类似的事情：

// for each 0 <= i < k generate a sequence of random numbers
val randomSeeds: Array[Array[Byte]] = ... ; // initialize by random sequences

def hash(i: Int, value: Array[Byte]): Array[Byte] = {
    val dg = java.security.MessageDigest.getInstance("SHA-1");
    // "seed" the digest by a random value based on the index
    dg.update(randomSeeds(i));
    return dg.digest(value);
    // if you need integer hash values, just take 4 bytes
    // of the result and convert them to an int
}

编辑： 我不知道 Count-Min Sketch 的精确要求，也许一个简单的 has 函数就足够了，但它似乎不是最简单的解决方案。

我建议使用加密散列函数，因为你有很强的保证，生成的散列函数会非常不同，而且很容易实现，只需使用标准库即可。

另一方面，如果您有两个形式为f1(x) = ax + b (mod p)和的散列函数，那么您可以使用一个简单的线性公式f2(x) = cx + d (mod p)（在不知道的情况下）使用另一个哈希函数来计算一个，这表明它们不是很独立。所以你可能会在这里遇到意想不到的问题。xf2(x) = c / a * (f1(x) - b) + d (mod p)

于 2012-08-25T09:01:58.777 回答