详解布隆过滤器，并教你自己实现一个布隆过滤器_如何定义一个布隆过滤器

最近在学习Redis缓存穿透等知识的时候看到了布隆过滤器可以用于解决缓存穿透问题，因此对布隆过滤器进行了学习，并记录下此篇笔记。

一、简介

根据百度百科可知，布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器主要由一个位标记数组和一系列随机映射函数（hash）组成，hash函数负责计算hash值，然后标记对应的标记位，因此就需要一个位标记数组了。

二、布隆过滤器的原理

布隆过滤器主要有几个过程：

• 添加元素
• 判断元素是否在过滤器中

1、添加元素

布隆过滤器在添加元素的时候，会进行如下操作：

• 第一步是会使用多个函数对元素计算hash值。
• 第二步是将这些计算出来的hash值对应的数组的位数给标记，一般是设为true。

流程图大概为如下：

2、判断元素是否在过滤器中

布隆过滤器在判断元素是否存在的时候，会进行如下操作：

• 第一步，使用hash函数分别对元素计算hash。
• 第二步，使用计算出来的hash去数组对应位数找此时的状态。
• 必须是全部状态都是true，该元素才是存在的，如果有一个状态false则不存在 。

流程图大概如下：

所以在判断元素是否存在的时候，我们可以直接拿hash对应的位数进行&操作，就可以得出是否存在了。

从上面的原理我们可以看出，如果布隆过滤器判断该元素存在，则该元素不一定存在，因为有可能是另一个字符串hash冲突导致的位数状态为true；但是如果布隆过滤器判断该元素不存在，则该元素一定不存在。

三、自己实现一个布隆过滤器

从上面我们可以得知，如果要实现一个布隆过滤器的话，需要实现以下：

• 一个位标记数组
• 多个hash函数
• 添加元素到布隆过滤器的方法
• 判断元素是否在布隆过滤器的方法

代码如下：

import java.util.BitSet;

/**
 * @ClassName MyBloomFilter
 * @Description 自己实现的布隆过滤器
 * @Author cxc
 * @Date 2020/10/6 15:57
 * @Verseion 1.0
 **/
public class MyBloomFilter {

    /**
     *  标记位数组的大小
     **/
    private static final int DEFAULT_SIZE = 2 << 24;

    /**
     * 根据这个数组来创建多个hash函数
     **/
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * 标记位数组
     **/
    private BitSet bitSet = new BitSet(DEFAULT_SIZE);

    /**
     * hash函数数组
     **/
    private SimpleHash [] simpleHashes = new SimpleHash[SEEDS.length];

    /**
     * @Description: 构造器
     * @Author: caixucheng
     * @Date: 2020/10/6 16:22
     * @version: v1.0.0
     **/
    public MyBloomFilter(){
        // 初始化hash数组
        for (int i = 0;i < SEEDS.length;++i){
            simpleHashes[i] = new SimpleHash(SEEDS.length,SEEDS[i]);
        }
    }


    /**
     * @Description: 将一个元素添加到布隆过滤器中
     * @Author: caixucheng
     * @Date: 2020/10/6 16:05
     * @param value: 元素
     * @version: v1.0.0
     **/
    public void add(Object value){
        // 分别计算value的hash值然后将对应的位置true
        for (SimpleHash s : simpleHashes){
            bitSet.set(s.hash(value),true);
        }
    }

    /**
     * @Description: 判断一个元素是否在布隆过滤器中
     * @Author: caixucheng
     * @Date: 2020/10/6 16:27
     * @param value: 元素
     * @return: boolean 存在则返回true，否则返回false
     * @version: v1.0.0
     **/
    public boolean isContain(Object value){
        boolean res = true;
        // 计算全部的hash值，看看是否全为true
        for (SimpleHash s : simpleHashes){
            res &= bitSet.get(s.hash(value));
        }
        return res;
    }

    /**
     * @Description: 静态内部类，用于实现hash
     * @Author: caixucheng
     * @Date: 2020/10/6 15:58
     * @version: v1.0.0
     **/
    public static class SimpleHash{

        private int cap;
        private int seed;

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

        /**
         * @Description: hash函数
         * @Author: caixucheng
         * @Date: 2020/10/6 16:00
         * @param value: 需要进行hash的值
         * @return: int 返回hash计算出来的值
         * @version: v1.0.0
         **/
        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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107