布隆过滤器原理，优缺点

介绍：

• 位图 ：int[ 10]，每个int类型的整数是4*8=32个bit，则int[10]⼀共有320 bit，每个bit⾮0即1，初始化时都是0
• 添加数据时 ：将数据进⾏ hash得到hash值 ，对应到bit位，将该bit改为 1 ，hash函数可以定义多个，则⼀个数据添加会将多个（hash函数个数）bit改为1，多个hash函数的⽬的是减少hash碰撞的概率
• 查询数据 ： hash函数计算得到hash值 ，对应到bit中，如果有⼀个为 0 ，则说明数据不在bit中，如果都为1 ，则该数据可能在bit中

---

优点：

• 占用内存小
• 增加和查询元素的时间复杂度为：O(K), (K为哈希函数的个数，⼀般⽐较⼩)，与数据量⼤⼩⽆关哈希函数相互之间没有关系，⽅便硬件并⾏运算
• 布隆过滤器不需要存储元素本身，在某些对保密要求⽐较严格的场合有很⼤优势 数据量很⼤时，布隆过滤器可以表示全集
• 使⽤同⼀组散列函数的布隆过滤器可以进⾏交、并、差运算

---

缺点：

• 误判率，即存在假阳性( False Position )，不能准确判断元素是否在集合中不能获取元素本身
• ⼀般情况下 不能从布隆过滤器中删除元素