布隆过滤器设计

Question

我想知道我在哪里可以找到布隆过滤器的实现，并对散列函数的选择做了一些说明。

此外，我有以下问题：
1）布隆过滤器已知有误报。是否有可能通过使用两个过滤器来减少它们，一个用于已使用的元素，一个用于未使用的元素（假设该集合是有限的并且先验已知的）并比较两者？
2）在CS文献中还有其他类似的算法吗？

Answer 1

我的直觉是通过使用反滤波器占用的额外空间来扩大正滤波器，可以更好地减少误报。

至于资源方面，3月8日从my course syllabus引用的论文将是有用的。

Answer 2

Bloom filter的Java实现可以从here找到。如果你不能查看它，我会把代码粘贴到下面（用中文评论）。

import java.util.BitSet; 

publicclass BloomFilter 
{ 
    /* BitSet初始分配2^24个bit */ 
    privatestaticfinalint DEFAULT_SIZE =1<<25; 
    /* 不同哈希函数的种子，一般应取质数 */ 
    privatestaticfinalint[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 }; 
    private BitSet bits =new BitSet(DEFAULT_SIZE); 
    /* 哈希函数对象 */ 
    private SimpleHash[] func =new SimpleHash[seeds.length]; 

    public BloomFilter() 
    { 
     for (int i =0; i < seeds.length; i++) 
     { 
      func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]); 
     } 
    } 

    // 将字符串标记到bits中 
    publicvoid add(String value) 
    { 
     for (SimpleHash f : func) 
     { 
      bits.set(f.hash(value), true); 
     } 
    } 

    //判断字符串是否已经被bits标记 
    publicboolean contains(String value) 
    { 
     if (value ==null) 
     { 
      returnfalse; 
     } 
     boolean ret =true; 
     for (SimpleHash f : func) 
     { 
      ret = ret && bits.get(f.hash(value)); 
     } 
     return ret; 
    } 

    /* 哈希函数类 */ 
    publicstaticclass SimpleHash 
    { 
     privateint cap; 
     privateint seed; 

     public SimpleHash(int cap, int seed) 
     { 
      this.cap = cap; 
      this.seed = seed; 
     } 

     //hash函数，采用简单的加权和hash 
     publicint hash(String value) 
     { 
      int result =0; 
      int len = value.length(); 
      for (int i =0; i < len; i++) 
      { 
       result = seed * result + value.charAt(i); 
      } 
      return (cap -1) & result; 
     } 
    } 
} 

在设计布隆过滤器而言，哈希函数的布隆过滤器需要多少可确定为here也闯民宅的Wikipedia article about Bloom filters，然后你发现误报的部分概率。本节解释散列函数的数量如何影响误报的概率，并给出用于根据期望的预期概率确定k的公式。的误报。从维基百科文章

---

引用：

显然，假 阳性的概率为m（比特阵列中的数 ）减小而增加，并且 增加为n（数插入的 元素）增加。为了最大限度地减少给定m和 N，K（散列 函数的数量）的值 概率

Answer 3

我认为，我们应该看看布隆过滤器的应用，秘密在名称中，它是一个过滤器而不是数据结构。它主要用于通过检查项目是否不是集合的一部分来节省资源。如果想要将误报最小化为0，则必须插入所有不属于该集合的项目，因为对于精心设计的布隆过滤器没有误报，除非布隆过滤器是巨大且不切实际的，不妨将这些项存储在跳过列表中:)如果有人对此感兴趣，我在Bloom Filters上写了一个简单的教程。

http://techeffigy.wordpress.com/2014/06/05/bloom-filter-tutorial/

Answer 4

它非常容易使用Java 8个功能来实现布隆过滤器。你只需要一个long[]来存储这些位，以及一些散列函数，你可以用ToIntFunction<T>来表示。我在doing this from scratch上做了简短的介绍。

要注意的部分是从数组中选择正确的位。

public class BloomFilter<T> { 

    private final long[] array; 
    private final int size; 
    private final List<ToIntFunction<T>> hashFunctions; 

    public BloomFilter(long[] array, int logicalSize, List<ToIntFunction<T>> hashFunctions) { 
     this.array = array; 
     this.size = logicalSize; 
     this.hashFunctions = hashFunctions; 
    } 

    public void add(T value) { 
     for (ToIntFunction<T> function : hashFunctions) { 
       int hash = mapHash(function.applyAsInt(value)); 
       array[hash >>> 6] |= 1L << hash; 
     } 
    } 

    public boolean mightContain(T value) { 
     for (ToIntFunction<T> function : hashFunctions) { 
       int hash = mapHash(function.applyAsInt(value)); 
       if ((array[hash >>> 6] & (1L << hash)) == 0) { 
        return false; 
       } 
     } 
     return true; 
    } 

    private int mapHash(int hash) { 
     return hash & (size - 1); 
    } 


    public static <T> Builder<T> builder() { 
     return new Builder<>(); 
    } 

    public static class Builder<T> { 
     private int size; 
     private List<ToIntFunction<T>> hashFunctions; 

     public Builder<T> withSize(int size) { 
      this.size = size; 
      return this; 
     } 

     public Builder<T> withHashFunctions(List<ToIntFunction<T>> hashFunctions) { 
       this.hashFunctions = hashFunctions; 
       return this; 
      } 

     public BloomFilter<T> build() { 
       return new BloomFilter<>(new long[size >>> 6], size, hashFunctions); 
     } 
    } 
}