布隆过滤器设计

Question

我想知道在哪里可以找到Bloom filter的实现，以及关于哈希函数选择的一些解释。

此外，我还有以下问题：

1)已知Bloom过滤器具有误报。是否可以通过使用两个过滤器来减少它们，一个用于使用的元素，另一个用于未使用的元素(假设集合是有限的，并且先验已知)，并比较这两个过滤器？

2) CS文献中还有其他类似的算法吗？

Answer 1

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

至于资源，来自my course syllabus的3月8日参考的论文将是有用的。

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

使用Java8特性实现Bloom filter非常容易。您只需要一个用来存储这些位的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);
         }
     }  
}