布隆过滤器
布隆过滤器
布隆过滤器就是测试一个元素是否属于一个集合。
特点
空间利用率高：布隆过滤器可以用较少的空间表示较大的集合。
**快速查找：**查询操作的时间复杂度为O(k),其中k是hash function的数量。
**存在误判：**它可能认为某个不在集合中的元素在集合中，但是不会出现某个在集中的元素说不在。（缺点，元素越多，错误率越高，不支持删除（改进版本如计数布隆过滤器可能支持））
结构
布隆过滤器由一个位数组和一组独立的hash function组成。他的工作原理是：
1.**初始化：**初始化一个大小为m的位数组，所有位都设置0。选择k哥独立的hash function。
- 添加元素： 对于每个要添加的元素，使用k个hash function分别计算该元素的k个hash值，将这个hash 值对应的位置都设置1.
- 查询元素： 对于查询的元素，同样适用k个hash函数计算其k个hash值，检查这个k个位置。如果所有位置都是1.则认为该元素可能存在集合中；如果任何一个位置为0，那么这个元素一定不在集合中。
模拟实现
假设你有一个集合，用来存储一些学生的名字，你需要快速判断一个名字是否在这个集合中。
假设你要添加名字"Alex"到集合中：
-
你使用哈希函数A对"Alex"进行哈希运算，得到值2。
-
使用哈希函数B对"Alex"进行哈希运算，得到值4。
-
使用哈希函数C对"Alex"进行哈希运算，得到值7
然后你把数组中第2、4、7位设为1。现在位数组可能是这样的：[0, 0, 1, 0, 1, 0, 0, 1, 0, 0]
这时候我们要查bob
- 使用哈希函数A对"Bob"进行哈希运算，得到值3。
- 使用哈希函数B对"Bob"进行哈希运算，得到值5。
- 使用哈希函数C对"Bob"进行哈希运算，得到值8。
然后你检查数组中第3、5、8位：
- 第3位是0
- 第5位是0
- 第8位是0
说明bob不在
这时候在查alex发现
使用哈希函数A对"Alex"进行哈希运算，得到值2。
使用哈希函数B对"Alex"进行哈希运算，得到值4。
使用哈希函数C对"Alex"进行哈希运算，得到值7。
所以alex在。
使用场景
网络缓存和数据库的快速查找。
黑名单过滤
爬虫对已访问URL的记录
分布式系统中的数据同步。
为什么存在错误判定
因为多个名字的hash值可能会碰撞，导致同一个位置被设置为1.但是布隆过滤器不会漏任何在集合中的元素。