布隆过滤器
布隆过滤器
什么是布隆过滤器
由一个初值为零的bit数组和多个哈希函数构成，用来快速判断集合中是否存在某个元素
布隆过滤器是一种类似set的数据结构，只是统计结果在巨量数据下有点小瑕疵，不够完美
特点
高效地插入和查询，占用空间少，返回的结果是不确定性+不够完美。
重点：一个元素如果判断结果：存在时，元素不一定存在（存在hash冲突），但是判断结果为不存在时，则一定不存在。
布隆过滤器可以添加元素，但是不能删除元素，由于涉及hashcode判断依据，删除元素会导致误判率增加。
底层原理
添加key时
使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置,每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。
查询key时
只要有其中一位是0就表示这个key不存在，但如果都是1，则不一定存在对应的key。
查询某个变量的时候我们只要看看这些点是不是都是1，就可以大概率知道集合中有没有它了如果这些点，有任何一个为零则被查询变量一定不在，
如果都是1，则被查询变量很可能存在，
为什么说是可能存在，而不是一定存在呢?那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。(见上图3号坑两个对象都1)正是基于布隆过滤器的快速检测特性，我们可以在把数据写入数据库时，使用布隆过滤器做个标记。当缓存缺失后，应用查询数据库时，可以通过查询布隆过滤器快速判断数据是否存在。如果不存在，就不用再去数据库中查询了。这样一来，即使发生缓存穿透了，大量请求只会查询Redis和布隆过滤器，而不会积压到数据库，也就不会影响数据库的正常运行。布隆过滤器可以使用Redis实现，本身就能承担较大的并发访问压力。
使用
初始化bitmap
添加占坑位
判断是否存在
为什么布隆过滤器不能删！
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的bit位被多次映射且置1。
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个bit并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素
特性
布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。
总结
是否存在：
有，是很可能有。 无 是肯定无，100%无
使用时最好不要让实际元素数量远大于初始化数量，一次给够避免扩容。当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个size更大的过滤器，再将所有的历史元素批量add进行
布隆过滤器的使用场景
解决缓存穿透的问题，和redis结合bitmap使用
缓存穿透是什么
一般情况下，先查询缓存redis是否有该条数据，缓存中没有时，再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。
缓存透带来的问题是，当有大量请球查询数据库不存在的数据时，就会给数据库带来压力,甚至会拖垮数据库。
可以使用布隆过滤器解决缓存穿透的问题
把已存在数据的key存在布隆过滤器中，相当于redis前面挡着一个布隆过滤器。
当有新的请求时，先到布隆过滤器中查询是否存在:
如果布隆过滤器中不存在该条数据则直接返回;
如果布隆过滤器中己存在，才去查询缓存redis，如果redis里没查询到则再查询Mysql数据库
黑名单校验，识别垃圾邮箱
发现存在黑名单中的，就执行特定操作。比如:识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。
假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。
把所有黑名单都放在布隆过滤器中，在收到邮件时，判断邮件地址是否在布隆过滤器中即寸。
安全连接地址，全球上10亿的网址判断
整体架构
构建过程
sebit的构建过程
@PostConstruct 初始化白名单数据----计算元素的hash值-----通过上一步hash值算出对应的二进制数组的坑位-----将对应坑位的值修改为数字1，表示存在getbit查询是否存在
计算元素的hash值----通过上一步hash值算出对应的二进制数组的坑位----返回对应坑位的值，0表示无，1表示存在
