java - 在 clojure 中构建布隆过滤器时要使用哪些散列技术？

Question

我想在 Clojure 中构建一个布隆过滤器，但我对基于 JVM 的语言可能可用的所有散列库知之甚少。

我应该使用什么来实现 Clojure 中最快(而不是最准确)的布隆映射实现？

Answer 1

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

Java 字符串已经内置了一个可以使用的哈希函数 - String.hashCode() with 返回一个 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 . hashcode 实现乍一看还不错，但它使用了一个字节数组，我认为它比使用 chars 效率低一些，因为需要处理字符编码开销。