生成k个成对独立的散列函数

Question

我正在尝试在Scala中实现Count-Min Sketch算法,因此我需要生成k个成对独立的散列函数.

这是我之前编程的任何一个低级别,除了Algorithms类之外我对哈希函数知之甚少,所以我的问题是:如何生成这些k成对独立哈希函数？

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

我看起来更简单而不是原始速度(例如,如果它更容易实现,我将采取5倍的速度).

Answer 1

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

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

Answer 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)，那么您可以使用另一个（在不知道 的情况下x）使用简单的线性公式 来计算一个f2(x) = c / a * (f1(x) - b) + d (mod p)哈希函数，这表明它们并不是非常独立。所以你可能会在这里遇到意想不到的问题。