BloomFilter 布隆过滤器

BloomFilter

定义： 空间效率高的概率型数据结构，用来检查一个元素是否在一个集合中

原理： 当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就 （大约） 知道集合中有没有它了

如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。

使用场景： 可用于解决网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题

布隆过滤器存储空间和插入/查询时间都是常数O(k)

BloomFilter算法

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。

假设位数组的长度为m，哈希函数的个数为k，保存数据只需要将哈希函数的结果值都置为1

1. BloomFilter算法推导见Bloom Filters - the math，Bloom_filter-wikipedia
2. 哈希函数数量最优化见Building a Better Bloom Filter

BloomFilter缺点

bloom filter之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性

• 存在误判。可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。
• 删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter

为了解决布隆过滤器中不能删除，且存在误判的缺点，新的哈希算法——cuckoo filter出现了。它既可以确保该元素存在的必然性，又可以在不违背此前提下删除任意元素，仅仅比bitmap牺牲了微量空间效率。Cuckoo filter

BloomFilter实现

对于一个确定的场景，我们预估要存的数据量为n，期望的误判率为fpp，然后需要计算我们需要的Bit数组的大小m，以及hash函数的个数k，并选择hash函数。下面是Guava Bloom Filter的实现

Bit数组大小选择

$m=$$-\frac{nlnfpp}{(ln2{)}^2}$

哈希函数个数选择

$k=$$\frac{m}{n}ln2$

哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数

BloomFilter应用

Guava BloomFilter

<dependency>
    <groupId>com.google.guavagroupId>
    <artifactId>guavaartifactId>
    <version>23.0version>
dependency>  

源码

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
        return create(funnel, (long) expectedInsertions);
}  

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
    return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}

public static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp) {
    return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}

static <T> BloomFilter<T> create(
  Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
 ......
}

调用

public class BloomFilterTest {

    private static int total = 1000000;
    private static BloomFilter<Integer> bf = BloomFilter.<Integer>create(Funnels.integerFunnel(), total);

    public static void main(String[] args) {
        bf.put(1);
        bf.mightContain(1);
    }
}

redis插件

Redis 4.0 的时候官方提供了插件机制，集成了布隆过滤器的模块

---

参考资料：

1. BloomFilter wiki
2. BloomFilter原理，实现及优化
3. BloomFilter算法
4. CuckooFilter wiki
5. CuckooFilter论文