java - 为 LSH Minhash 算法生成随机哈希函数

Question

我正在用 Java 编写一个 minhashing 算法，它要求我生成任意数量的随机哈希函数(在我的例子中是 240 个哈希函数)，并通过它运行任意数量的整数(目前是 2000 个)。

为了做到这一点，我一直在为 240 个哈希函数中的每一个生成随机数 a、b 和 c(从 1 到 2001 的范围)。然后，我的哈希函数返回 h = ((a*x) + b) % c，其中 h 是返回值，x 是贯穿它的整数之一。

这是随机哈希的有效实现，还是有更普遍/更可接受的方法？

这篇文章问了一个类似的问题，但我仍然对答案的措辞感到困惑:Minhash implementation how to find hash functions for permutations

Answer 1

几年前我在使用 Bloom 过滤器时，偶然看到一篇文章，其中描述了如何使用最少的代码非常简单地生成多个哈希函数。他描述的方法非常有效。参见 Less Hashing, Same Performance: Building a Better Bloom Filter .

基本思路是创建两个哈希函数，分别命名为h1和h2，然后可以模拟多个哈希函数，g1 通过 gk，使用公式:

gi = h1(x) + i*h2(x)

i 从 1 到 k(您想要的哈希函数的数量)。

这篇论文非常值得一读，即使您决定不实现他的想法。尽管在阅读之后我无法想象不想实现它。它使我的 Bloom 过滤器代码更易于处理，并且不会对性能产生负面影响。