布隆过滤器BloomFilter

BloomFilter

1. 参考资料

吴军《数学之美》
布隆过滤器详解

2. 应用场景: 判断一个元素是否在一个已知的集合中！

布隆过滤器是由Burton Bloom在1970年提出的, 可以用来判断一个元素是否在一个已知的集合中。例如:

    1. 字处理软件中检查一个单词是否拼写正确(单词是否在已知的词典中)
    1. FBI核实一个嫌疑人是否在已有的嫌疑犯名单上
    1. 网络爬虫中确认一个URL是否已经访问过
    1. 邮件系统确定一个邮件发件人地址是否为垃圾邮箱地址

布隆过滤器只需要散列表的1/8到1/4的大小就能解决同样的问题, 但是同时它也牺牲了部分准确度。
布隆过滤器的优点在于速度快、省空间、使用方便，缺点是有一定的误判率。
以FBI黑名单为例, 布隆过滤器绝对不会漏掉黑名单中任何一个疑犯, 但是有极小的可能会把一个不在黑名单中的人误判为嫌疑人。补救的办法是再建立一个白名单, 存储那些可能被误判的信息。

3. 布隆过滤器的简单实现

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package com.quantums.algorithm.search;

import java.util.BitSet;

/**
 * 布隆过滤器
 *
 */
public class BloomFilter {
    private final static int DEFAULT_CAP = 1 << 10; //BloomFilter的默认数组长度
    private BitSet bitSet = new BitSet(DEFAULT_CAP);
    private final static int[] seeds = {7, 11, 13, 17, 19, 23, 29, 31, 37, 53};
    private static SimpleHashAlgorithm[] hashs = new SimpleHashAlgorithm[seeds.length];

    private static void buildHashAlogrithms() {
        for (int i = 0; i < seeds.length; i++) {
            hashs[i] = new SimpleHashAlgorithm(DEFAULT_CAP, seeds[i]);
        }
    }

    public BloomFilter() {
        buildHashAlogrithms();
    }

    public void add(String val) {
        if (val == null) return;

        for (SimpleHashAlgorithm al : hashs) {
            bitSet.set(al.hash(val), true);
        }
    }

    public boolean contains(String str) {
        if (str == null) return false;

        for (SimpleHashAlgorithm al : hashs) {
            if (!bitSet.get(al.hash(str))) return false;
        }
        return true;
    }


    public static void main(String []ar){
        String[] origins = {"JAVA", "Linux","Go","C","Python","Shell"};
        BloomFilter bloomFilter = new BloomFilter();
        for(String s:origins){
            bloomFilter.add(s);
        }

        String[] tests = {"JAVA", "Linux","Go","C","Python","Shell","China","USA","Germany","UK","Keroa"};
        for (String s:tests){
            System.out.println(s+" "+bloomFilter.contains(s));
        }


    }

}


class SimpleHashAlgorithm {
    private int cap;
    private int seed;

    public SimpleHashAlgorithm(int c, int s) {
        this.cap = c;
        this.seed = s;
    }


    public int hash(String str) {
        int result = seed;
        for (int i = 0; i < str.length(); i++) {
            result = seed * result + str.charAt(i);
        }

        return (cap - 1) & result;
    }

}

执行结果:

1
2
3
4
5
6
7
8
9
10
11
JAVA true
Linux true
Go true
C true
Python true
Shell true
China false
USA false
Germany false
UK false
Keroa false