在clojure中构建bloom过滤器时要使用哪种散列技术？

Question

我想在Clojure中构建一个bloom过滤器,但我对基于JVM的语言可用的所有散列库知之甚少.

在Clojure中,我应该使用什么来实现最快(而不是最精确)的bloom map实现？

Answer 1

看一下Apache Cassandra中的Bloom Filter实现.这使用非常快的MurmurHash3算法,并以不同的方式组合两个哈希(或相同哈希的两个部分,因为升级到MurmurHash3而不是MurmurHash2)来计算所需的哈希数.

本文描述了组合生成方法

这是Cassandra源代码的一个片段:

    long[] hash = MurmurHash.hash3_x64_128(b, b.position(), b.remaining(), 0L);
    long hash1 = hash[0];
    long hash2 = hash[1];
    for (int i = 0; i < hashCount; ++i)
    {
        result[i] = Math.abs((hash1 + (long)i * hash2) % max);
    }

另请参阅Bloomfilter和Cassandra =为什么使用以及为什么要多次使用？

Answer 2

因此，布隆过滤器的有趣之处在于，为了有效工作，它们需要多个哈希函数。

Java 字符串已经内置了一个哈希函数，您可以使用它 - String.hashCode()返回 32 位整数哈希值。对于大多数用途来说，这是一个不错的哈希码，并且这可能已经足够了：例如，如果您将其划分为 2 个单独的 16 位哈希码，那么这可能足以让您的布隆过滤器正常工作。您可能会遇到一些冲突，但这没关系 - 布隆过滤器预计会发生一些冲突。

如果没有，您可能想要自己动手，在这种情况下，我建议使用String.getChars()来访问原始字符数据，然后使用它来计算多个哈希码。

帮助您入门的 Clojure 代码（仅总结字符值）：

(let [s "Hello"
      n (count s)
      cs (char-array n)]
  (.getChars s 0 n cs 0)
  (areduce cs i v 0 (+ v (int (aget cs i)))))
=> 500

请注意使用 Clojure 的 Java 互操作来调用 getChars，并使用 areduce 为您提供对字符数组的非常快速的迭代。

您可能还对我在 Github 上找到的 Java 布隆过滤器实现感兴趣： https: //github.com/MagnusS/Java-BloomFilter。乍一看，哈希码实现看起来不错，但它使用字节数组，我认为它比使用字符效率低一些，因为需要处理字符编码开销。