布隆过滤器

什么是布隆过滤器

我们可以把布隆过滤器看作有二进制向量或者说位数组和一系列随即映射函数零部分组成的数据结构。相比于我们平时用到的List、Map、Set等数据结构，它占用的空间更少并且效率更高，但其缺点是返回结果是概率性的，而不是非常准确。理论上添加到集合中的元素越多，误报的可能性也就越大。并且存放在布隆过滤器中的数据不易删除。

实现原理

当一个元素加入布隆过滤器中的时候，会进行如下操作：

1.使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数就得到几个哈希值）。
2.根据得到的哈希值，在位数组中把对应下标的值置为1。

当我们需要判断一个元素是否存在于布隆过滤器中的时候，会进行如下操作：

1.对给定的元素进行哈希计算。
2.得到值之后判断数组中的每个元素是否都为1，如果值都为1，那么说明在这个值存在布隆过滤器中，如果存在一个值不为1，说明该元素不存在布隆过滤器中。

不同的字符串的出来的哈希值可能一样，这种情况下，我们可以增加位数组大小或者调整哈希函数。

所以，我们可以得出结论：布隆过滤器说存在某个元素可能会误判但是如果说某个元素不存在，那么这个元素就一定不存在。

使用场景

1. 判断给定数据是否存在：比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5 亿以上！）、 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

2. 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

代码实现

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

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

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

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