在clojure中构建布隆过滤器时使用什么散列技术？

我想在Clojure中构建一个布隆过滤器，但对于基于JVM的语言可能提供的所有哈希库没有太多的知识。在clojure中构建布隆过滤器时使用什么散列技术？

在Clojure中，我应该如何使用最快速的（而不是最准确的）布卢姆图实现？

2012-03-04 jdoig

什么类型的数据是你的钥匙？字符串？字节数组？整型？ UUID的？ – pmdj 2012-03-04 10:33:56

我正在测试一组字符串的成员身份 – jdoig 2012-03-04 10:37:28

您可以尝试重复将混合哈希函数应用于字符串上由'hash（）'方法报告的内置哈希值。 http://www.cris.com/~Ttwang/tech/inthash.htm生成的值可能过于相关，这可能会导致布隆过滤器无效。我过去使用的方法是使用具有很长结果的散列函数（如SHA-256），并将结果拆分为块。这可能对您而言太慢。最简单的做法可能就是搜索“字符串散列函数”并实现一些结果。 – pmdj 2012-03-04 11:04:42

所以关于布隆过滤器的有趣之处在于，要有效地工作，他们需要多个哈希函数。

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 bloom filter实现：https://github.com/MagnusS/Java-BloomFilter。散列码实现乍一看看起来不错，但它使用了一个字节数组，我认为它比使用字符有点低效，因为需要处理字符编码开销。

来源

2012-03-04 10:59:34 mikera

在Java中编写了一个Bloom Filter（问题是关于JVM和哈希算法），不需要多个哈希函数。事实上（见下面的答案），一个好的MumurHash非常适合Bloom滤波器，因为它们速度非常快，碰撞的次数增加并不是一个真正的因素，因为布洛姆滤波器无论如何本质上都有假阳性率。Set中的数据类型也是不相关的，因为性能和管理误报率的最佳实践是通过散列输入密钥来平滑比特集分布。 – 2013-05-28 17:46:09

@Darrell - 你需要足够的独立计算*位*，以便将结果分割成多个散列函数。这就是下面的答案 - 我将其定义为“使用多个散列函数”:-) – mikera 2013-05-29 00:28:44

问题是关于“哈希库可能适用于基于JVM的语言”，所以评论是参考那些与“数字散列桶'的使用/计算。我认为短语'散列函数'意味着一个函数或方法（实现），而下面的注释说'计算所需的散列数'。对不起，任何困惑，但希望这澄清新用户，因为这是一个相当沉重的计算机科学的话题。 – 2013-05-31 13:14:14

查看Apache Cassandra中的Bloom Filter实现。这使用非常快的算法并且以不同的方式组合了两个散列（或者相同散列的两个部分，因为升级到MurmurHash3而不是MurmurHash2）以计算期望的散列数量。

的组合生成方法是this paper

描述，这里是从卡桑德拉源代码片段：

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 and Cassandra = Why used and why hashed several times?

来源

2012-03-04 11:18:49 DNA

在clojure中构建布隆过滤器时使用什么散列技术？

回答

相关问题