目录
一、布隆过滤器BloomFilter
1.1、面试题
1.2、 布隆过滤器简介
1.2.1、设计思想
1.3、特点
1.4、布隆过滤器原理
1.4.1、实现原理与数据结构
1.4.2、添加key、查询key
1.4.3、hash冲突导致数据不精准
1.4.4、三步骤
1.4.5、布隆过滤器误判，为什么不要删除
1.4.6、小结
1.5、使用场景
1.6、实现布隆过滤器
1.6.1、架构设计
1.6.2、步骤设计
1.6.3、实现springboot+redis7+mybatis实现基础案例
1.6.4、布隆过滤器加bitmap
1.7、布隆过滤器的优缺点
如何判断2亿个电话是否已经存在？
1、通过数据查询----数据量太大速度慢
2、数据预防在内存集合中:内存太大。
由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断集合中存在某个元素
1.2.1、设计思想
目的：减少内存占用
方式：不保存数据，只是在内存中做一个是否存在的标记flag
本质就是判断具体数据是否存在于一个大的集合中。
注意：
布隆过滤器是一种类似set的数据结构，只是统计结果在巨量数据下不够完美。
1、高效地插入和查询，占用空间少，返回地结果是不确定性和不够完美。
一个元素如果判断结果存在时，元素不一定存在，但判断结果为不存在时，则一定不存在。
3、布隆过滤器可以添加元素，但是不能删除元素，由于涉及hashcode判断依据，删掉元素会导致误判率增加。
1.4.1、实现原理与数据结构
原理：
布隆过滤器是一种专门用来解决去重问题的高级数据结构。
本质上是一个大型位数组和几个不同的无偏hash函数(无偏即分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成，用来快速判断某个数据是否存在。但是根hyperloglog一样，它也一样有那么一点点不精确，存在一定的误判率。
1.4.2、添加key、查询key
添加key：
使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置1都完成add操作。
查询key：
只要有其中一位是零就表示这个key不存在，如果都是1，则不一定存在对应的key。
结论：有，是可能有，无，是一定无
1.4.3、hash冲突导致数据不精准
使用Java代码模拟
1.4.4、三步骤
初始化bitmap：
布隆过滤器本质上是由长度为m的位向量或位列表组成，最初值均设置为0
添加占坑位：
当我们向布隆过滤器中添加数据时，为了尽量地址不冲突，会使用多个hash函数对key进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。 再把位数组的这几个位置都置为1就完成了add操作。
例如，我们添加一个字符串wmyskxz，对字符串进行多次hash(key)→取模运行→得到坑位。判断是否存在：
向布隆过滤器查询某个key是否存在时，先把这个key通过相同的多个hash函数进行运算，查看对应的位置是否都为1,只要有一个位为零，那么说明布隆过滤器中这个key不存在;
如果这几个位置全都是1，那么说明极有可能存在;
因为这些位置的1可能是因为其他的key存在导致的，也就是前面说过的hash冲突。。。
就比如我们在add了字符串wmyskxz数据之后，很明显下面1/3/5这几个位置的1是因为第一次添加的wmyskxz而导致的;
此时我们查询一个没添加过的不存在的字符串inexistent-key,它有可能计算后坑位也是1/3/5，这就是误判了.....
1.4.5、布隆过滤器误判，为什么不要删除
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竞是哪个输入产生的，因此误判的根源在于相同的bit 位被多次映射且置1。
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。
如果我们直接删除这一位的话，会影响其他的元素
特性：
布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。
1.4.6、小结
1、是否存在：有，不一定有，无，一定无
2、使用时最好不要让实际元素数量大于初始化数量，一次给够避免扩容。
3、当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个size更大的容器，在将所有历史元素批量add进行。
1、解决缓存穿透的问题，和redis结合bitmap使用。
2、黑名单校验，识别垃圾短信
3、安全连接网址判断
1.6.1、架构设计
Java -----》布隆过滤器 ---》redis ----》mysql
1.6.2、步骤设计
setBit的构建：
1、@PostConstruct初始化白名单数据
2、计算元素的hash值
3、通过hash值算出对应的二进制数组坑位
4、将对应坑位的值修改为数字1，表示存在
getBit查询是否存在：
1、计算元素的hash值
2、通过hash值算出对应的二进制数组的坑位
3、返回对应坑位的值，0表示无，1表示存在
1.6.3、实现springboot+redis7+mybatis实现基础案例
sql表
pom文件
config.properties
generatorConfig.xml
使用 generator生成实体类与mapper文件如下
修改pom
修改主启动类
service
controller
1.6.4、布隆过滤器加bitmap
优点：
高效的插入和查询，内存占用bit空间小
缺点：
1、不能删除元素，因为删掉元素会导致误判率增加，因为hash冲突同一位置可能存在的数据是多个共享的，你删除一个元素的同时可能也把其它的删除掉。