Bloom Filter

Bloom Filter

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。

它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在一个集合中。

它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

布隆过滤器速成

布隆过滤器在本质上是二进制向量。在高层级上，布隆过滤器以下面的方式工作：

添加元素到过滤器。

对元素进行几次哈希运算，当索引匹配哈希的结果时，将该位设置为 1 的。

如果要检测元素是否属于集合，使用相同的哈希运算步骤，检查相应位的值是1还是0。这就是布隆过滤器明确元素不存在的过程。如果位未被设置，则元素绝不可能存在于集合中。

当然，一个肯定的答案意味着，要不就是元素存在于集合中，要不就是遇见了哈希冲突。

注意

1. 一个值，设置了多个 hash，也就是存储了多个位置。这样为了提高准确性。

特点

所以布隆过滤有以下几个特点：

1. 只要返回数据不存在，则肯定不存在。

2. 返回数据存在，但只能是大概率存在。

3. 同时不能清除其中的数据。

应用场景

判断大量元素中包含一个数：

网页爬虫对URL的去重，避免爬取相同的URL地址；

反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）；

缓存击穿，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

使用布隆过滤器优化SQL查询

Guava BloomFliter 使用

引入 jar

  [xml]

1
2
3
4
5
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>14.0.1</version>
</dependency>

测试 demo

• Person.java

  [java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Person {

    public int id;
    public String firstName;
    public String lastName;
    public int birthYear;

    public Person(int id, String firstName, String lastName, int birthYear) {
        this.id = id;
        this.firstName = firstName;
        this.lastName = lastName;
        this.birthYear = birthYear;
    }
}

• BloomFilter.java

  [java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class BloomFilterTest {

    Funnel<Person> personFunnel = new Funnel<Person>() {
        @Override
        public void funnel(Person person, PrimitiveSink into) {
            into.putInt(person.id)
                    .putString(person.firstName, Charsets.UTF_8)
                    .putString(person.lastName, Charsets.UTF_8)
                    .putInt(person.birthYear);
        }
    };

    @Test
    public void test() {
        BloomFilter<Person> friends = BloomFilter.create(personFunnel, 500, 0.01);
        for (Person friend : personList()) {
            friends.put(friend);
        }

        Person dude = new Person(1, "1", "1", 1);

        // much later
        if (friends.mightContain(dude)) {
            // the probability that dude reached this place if he isn't a friend is 1%
            // we might, for example, start asynchronously loading things for dude while we do a more expensive exact check
            System.out.println("也许存在哦。。。");
        }
    }

    private List<Person> personList() {
        Person person = new Person(1, "1", "1", 1);
        Person person2 = new Person(2, "1", "1", 1);
        Person person3 = new Person(3, "1", "1", 1);
        Person person4 = new Person(4, "1", "1", 1);

        return Arrays.asList(person, person2, person3, person4);
    }

}

测试结果输出：

  [plaintext]

1
也许存在哦。。。

算法原理和复杂度

参考 wiki

回顾

上一节我们简单介绍了 BloomFilter 的原理，并且介绍了 guava BloomFilter 的使用。

今天让我们更上一层楼，实现一个属于自己的 BoolFilter。

实现原理

原理回顾

布隆过滤器在本质上是二进制向量。

在高层级上，布隆过滤器以下面的方式工作：

添加元素到过滤器。

对元素进行几次哈希运算，当索引匹配哈希的结果时，将该位设置为 1 的。

如果要检测元素是否属于集合，使用相同的哈希运算步骤，检查相应位的值是1还是0。这就是布隆过滤器明确元素不存在的过程。如果位未被设置，则元素绝不可能存在于集合中。

当然，一个肯定的答案意味着，要不就是元素存在于集合中，要不就是遇见了哈希冲突。

实现思路

我们再加入一个元素时，通过多种不同的 hash 算法，然后设置到 bit 数组中。

判断是否存在的时候，也对元素采用多种不同的 hash 算法，如果都为 true，则说明可能存在。如果有不为 true 的，说明一定不不存在。

自己实现简单版本

hash 算法

可以参考 hash 算法介绍

• IHash.java

  [java]

1
2
3
4
5
6
7
8
9
10
public interface IHash {

    /**
     * 根据 key 获取对应的hash值
     * @param key 字符串
     * @return hash 值
     */
    int hashIndex(final String key);

}

三个简单的实现：

• HashOne

  [java]

1
2
3
4
5
6
7
8
9
10
11
12
13
public class HashOne implements IHash {

    @Override
    public int hashIndex(String key) {
        int hash = 0;
        for(int i = 0; i < key.length(); i++) {
            hash = 33 * hash + key.charAt(i);
        }

        return Math .abs(hash);
    }

}

• HashTwo

  [java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class HashTwo implements IHash {

    @Override
    public int hashIndex(String key) {
        final int p = 16777619;
        int hash = (int) 2166136261L;

        for(int i = 0 ; i < key.length(); i++) {
            hash = (hash ^ key.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash);
    }
}

• HashThree

  [java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class HashThree implements IHash {

    @Override
    public int hashIndex(String key) {
        int hash, i;

        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }

        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return Math.abs(hash);
    }
}

Bloom Fliter 实现

• IBloomFilter.java

  [java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface IBloomFilter {

    /**
     * 添加一个元素
     * @param key  元素
     */
    void add(final String key);

    /**
     * 可能包含元素
     * @param key 元素
     * @return 可能包含
     */
    boolean mightContains(final String key);

}

• SimpleBloomFilter.java

  [java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import com.github.houbb.guava.learn.bloom.hash.HashOne;
import com.github.houbb.guava.learn.bloom.hash.HashThree;
import com.github.houbb.guava.learn.bloom.hash.HashTwo;

public class SimpleBloomFilter implements IBloomFilter {

    private final int size;

    private boolean[] array;

    public SimpleBloomFilter(int size) {
        this.size = size;
        this.array = new boolean[size];
    }

    @Override
    public void add(String key) {
        // 做三次 hash
        int hashOne = new HashOne().hashIndex(key);
        int hashTwo = new HashTwo().hashIndex(key);
        int hashThree = new HashThree().hashIndex(key);

        this.array[hashOne%array.length] = true;
        this.array[hashTwo%array.length] = true;
        this.array[hashThree%array.length] = true;
    }

    @Override
    public boolean mightContains(String key) {
        // 做三次 hash
        int hashOne = new HashOne().hashIndex(key);
        int hashTwo = new HashTwo().hashIndex(key);
        int hashThree = new HashThree().hashIndex(key);

        if(!array[hashOne]) {
            return false;
        }
        if(!array[hashTwo]) {
            return false;
        }
        if(!array[hashThree]) {
            return false;
        }

        return true;
    }
}

小结

当然我们实现版本的性能比较差，可以参考下 guava 的实现。

本文简单介绍了布隆过滤器的发展历史和应用场景，并给出了 guava BloomFliter 使用案例。希望大家对 bloom filter 有一个最基本的认识。

下一节我们将和大家一起实现属于自己的布隆过滤器。

觉得本文对你有帮助的话，欢迎点赞评论收藏关注一波。你的鼓励，是我最大的动力~

不知道你有哪些收获呢？或者有其他更多的想法，欢迎留言区和我一起讨论，期待与你的思考相遇。

参考资料

布隆过滤器

如何判断一个元素在亿级数据中是否存在？

• Guava

Google Guava 中的布隆过滤

GUava hash

• Bit 数组

https://blog.csdn.net/zimu666/article/details/8284906

https://blog.csdn.net/zimu666/article/details/8295724

https://www.cnblogs.com/varlxj/p/5168157.html

https://yuhuang-neil.iteye.com/blog/1190574

• Bloom Filter
  • 布隆过滤器速成
  • 特点
• 应用场景
• Guava BloomFliter 使用
  • 引入 jar
  • 测试 demo
• 算法原理和复杂度
• 回顾
• 实现原理
  • 原理回顾
  • 实现思路
• 自己实现简单版本
  • hash 算法
  • Bloom Fliter 实现
• 小结
• 参考资料