一、背景
无论是红黑树、平衡二叉树、散列表，结点都是存储的key-value对。而有些场景，内存是有限的，仅需要了解key是否存在，不想知道具体内容（value）。
这时就需要布隆过滤器。布隆过滤器是一种概率型数据结构，它的特点是高效的插入和查询，能确定某个字符串一定存在或者可能存在。
布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但误差可控，同时不支持删除操作。
（1）一个巨大的数据文件，需要知道是否存在某个key，如果把整个文件读取进行查找，这个效率就比较低。那么可以添加一个布隆过滤器，插入数据时对key做标识，查询key是否存在时直接查询布隆过滤器。
（2）一个数据库查询，想要查询数据库中是否存在key，可以添加一个布隆过滤器，查询key时直接查询布隆过滤器，不需要IO操作，大大提升查询效率。
二、布隆过滤器的构成
布隆过滤器的原理本质上和散列表是一样的。但布隆过滤器为了节约内存，不是使用的数组，而是使用的位图。
（1）位图。
bit的数组，实现方式有多种。
代码语言：javascript复制// 例如
vector<char> bitmap;
uint64_t bitmap;（2）n个hash函数。
举例： 使用byte buf[8]构建64bit的位图，那么n=i*8 j；假设hash(key)=173，n=173d=173&63=45，j=n%8=45%8=5，i=n/8=45/8=5。因此将（5，5）位置置 1。
bit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
0 | |||||||||
1 | |||||||||
2 | |||||||||
3 | |||||||||
4 | |||||||||
5 | 1 | ||||||||
6 | |||||||||
7 | |||||||||
8 |
三、原理
当一个元素加入位图时，通过k个hash函数将元素映射到位图的k个点，并把它们置1；当检索时，再通过k个hash函数运算检查位图的k个点是否都为1；如果有不为1的点，那么认为该key不存在；如果全部为1，则可能存在。
布隆过滤器是不支持删除操作的，原因在于：在位图中每个槽位只有两种状态（0或者1），一个槽位被置为1，但不确定它被设置了多少次；也不知道被多少个key hash映射而来；以及具体被哪个hash函数映射而来。
值得注意的是，只要有一个槽位为0，则key一定不存在；如果key映射的所有槽位都为1，不能说明一定存在，只能说明可能存在（假阳率）。
图片四、应用场景
布隆过滤器通常用于判断某个key一定不存在的情况。同时允许判断存在时有误差的情况。
常见处理场景：
（1）缓存穿透的解决。
（2）热key限流。
缓存场景：为了减轻数据库（MySQL）的访问压力，在数据库（MySQL）和服务端（server）直接加入缓存用来存储热点数据。
缓存穿透：服务端（server）请求数据时，缓存和数据库都不包含数据，最终请求压力全部涌向数据库。
数据请求步骤：
先访问redis，如果存在则直接返回，如果不存在则走2访问数据库；
访问数据库，如果不存在直接返回，如果存在则将MySQL存在的key写回redis。
发生原因：黑客利用漏洞伪造数据攻击或内部业务bug造成大量重复请求不存在的数据。
解决方案：
（1）在redis设置<key，null>键值对，依次避免访问数据库；缺点是<key，null>过多会占用过多内存，可以给key设置过期expire key 600ms，停止攻击后最终由redis自动清除无用的key。
（2）在服务端（server）存储一个布隆过滤器，将MySQL存在的key放入布隆过滤器中，布隆过滤器可以过滤一定不存在的数据。
五、应用分析
在实际应用中，该选择多少个 hash 函数？要分配多少空间的位图？预期存储多少元素？如何控制误差？
可以使用如下公式计算：
n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));
其中
n -- 预期布隆过滤器中元素的个数，如上图 只有str1和str2 两元素 那么 n=2
p -- 假阳率，在0-1之间 0.000000
m -- 位图所占空间
k -- hash函数的个数
数学公式：
图片5.1、变量关系
假设：
n = 6000
p = 0.000000001
m = 258797 (31.59KiB)
k = 30
得到如下关系图：
图片（1）假阳率p会随着插入元素的增多而逐渐变高。
（2）假阳率p会随着位图所占空间的增大而减小。
（3）假阳率p会随着hash函数个数增多，呈现快速减小后缓慢增长的趋势。hash函数个数在31时假阳率最低。
5.2、确定n和p
在实际使用布隆过滤器时，首先需要确定 n 和 p，通过上面的运算得出 m 和 k；推荐一个布隆过滤器计算器可以选出合适的值。
5.3、选择hash函数
选择一个 hash 函数，通过给 hash 传递不同的种子偏移值，采用**线性探寻**的方式构造多个 hash 函数；
代码语言：javascript复制#define MIX_UINT64(v) ((uint32_t)((v>>32)^(v)))
uint64_t hash1 = MurmurHash2_x64(key, len, Seed);
uint64_t hash2 = MurmurHash2_x64(key, len,MIX_UINT64(hash1));
for (i = 0; i < k; i ) // k 是hash函数的个数
{
Pos[i] = (hash1 i*hash2) % m; // m 是位图的⼤⼩
}六、总结
- 布隆过滤器由位图和n个hash函数构成。布隆过滤器的操作是一个key经过多个hash函数，然后对位图大小进行取余等到多个槽位并对应置为1。判断时只要有一个槽位为0就一定不存在该key。
- 布隆过滤器能确定一个key一定不存在，不能判断key一定存在，但可控假阳率确定存在。
- 布隆过滤器不支持删除操作，可以通过两个布隆过滤器解决（依然存在假阳率，但会低一些），添加放在第一个布隆过滤器，删除放在第二个布隆过滤器。即要判断key是否存在，首先检查第二个布隆过滤器是否删除过，如果删除过就往第一个布隆过滤器插入。
- 布隆过滤器根据n和p算出m和k，hash函数个数是利用开放寻址法来计算的。
