4、布隆过滤器

一、定义

由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断某个数据是否存在

二、作用

本质就是判断具体数据存不存在一个大的集合中

布隆过滤器是一种类似set的数据结构，只是统计结果不太准确

三、特点

• 高效地插入和查询，占用空间少，返回的结果是不确定性的。

• 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。

• 布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。

• 误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判。

四、使用场景

• 解决缓存穿透

• 黑名单校验

五、布隆过滤器误判率

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，
因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。
如果我们直接删除这一位的话，会影响其他的元素

这里是和发生hash冲突的数据结构有关，发生了hash冲突，冲突的数据组合为一个链表，一个key可能对应着多个数据

特性

一个元素判断结果为没有时则一定没有，
如果判断结果为存在的时候元素不一定存在。

布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。

六、优缺点

优点

高效的插入和查询，占用更少的空间

缺点

不能删除数据，可能会增加误判率

存在误判，发生hash冲突，不同的数据可能会出现相同的值

七、使用建议

• 当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进行

  原因是因为布隆过滤器不能删除数据，删除数据可能会造成删除多个值，使得误判率增加