小编典典

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

algorithm

我正在用Java编写minhashing算法,该算法要求我生成任意数量的随机哈希函数(在我的情况下为240个哈希函数),并通过它运行任意数量的整数(此刻为2000)。

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

这是随机散列的有效实现,还是有更通用/可接受的方式呢?


阅读 313

收藏
2020-07-28

共1个答案

小编典典

几年前,当我使用Bloom过滤器时,遇到了一篇文章,描述了如何使用最少的代码非常简单地生成多个哈希函数。他描述的方法效果很好。见少散列,同样的性能:建立一个更好的布隆过滤器

基本思想是创建两个哈希函数,分别将其称为h1h2,然后可以使用,g1通过gk使用以下公式来模拟多个哈希函数:

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

i从1到k(所需的哈希函数数)之间变化。

即使您决定不执行他的想法,该论文也很值得阅读。尽管阅读完之后我无法想象不想实现它。它使我的Bloom过滤器代码更易于处理,并且对性能没有负面影响。

2020-07-28