布隆过滤器
Last updated
Last updated
布隆过滤器的本质是一组哈希算法算法和 bitmap 的组合
当我们想要快速判断一个元素是否在一个集合中时，首先想到的数据结构一定是 hashmap，但 hashmap 非常占空间。
其次会想到 bitmap。bitmap 将整数元素的值作为数组的下标，通过数组上值为 0/1 来标记元素存在。但 bitmap 有两个问题：
只适用于整数
如果集合稀疏，但跨度很大，也会占很多空间，造成浪费（比如只有 4000,000,000 这 1 个数，然而这一个数就需要开 40亿 的空间）
为此 BURTON H. BLOOM 在 1970年提出了一个观点，他认为如果使用的场景可以容忍假阳性错误，那么是存在空间消耗小且运行时间还快的算法（数据结构）的。其中第二种结构，因其在时空上更占优势而被我们熟知，该结构被后人称为 "Bloom Filter"。
使用多个哈希函数将 key 映射到一个比特数组中的多个位置（可能冲突）并设值为1。
查询时计算相同哈希。
如果有某位为0，则说明被查 key 一定不存在。否则元素很可能在集合
CBF支持计数，可以用于网络缓存优化
dlCBF是CBF的改进版，有更小的存储空间
Spatial-BF支持多个集合，配合同态加密使用可以用于户隐私保护
Scalable-BF支持自动扩容，被Redis作为其布隆过滤器的内部实现。
布隆过滤器中的哈希函数选择也是有学问题的，应该选在那些分布均匀计算速度快的，比如Murmur3。
| BloomFilter | Counting Bloom Filter(CBF) | Spatial Bloom Filters | Scalable Bloom Filters | |
|---|---|---|---|---|
描述 | 将布隆过滤器比特数组的1为拓展为多位用于计数。插入时，如果冲突就给计数器+1 | 将一个集合改为多个集合 | 当集合元素数量接近阈值时，扩容一个新布隆过滤器来记录新数据。查询时需要判断多个布隆过滤器。Redis是用的就是这款 | |
改进点 | 支持计数、删除 | 支持多集合 | 自动扩容 | |
时间复杂度 | O(K) | O(K) | O(K) | 插入: O(K) 查询: O(K0 + ... + Kn) |
空间复杂度 | O(M) | O(M*c) | O(M*c) | O(M0 + ... + Mn) |
M: 布隆过滤器比特数组长度
K：哈希函数个数
c：计数的位数
假设数组长度为 m，hash 函数个数为 k
某一位被置为 1 的概率：
某一位没有被置为 1 的概率（为 0 的概率）
k 次 hash 后都没有被置为 1 的概率（k 次 hash 均为 0）
使用 1/e 的等价交换：
带入得：
如果插入了 n 个元素，某一位仍然为 0 的概率:
取反，在插入 n 个元素后，某一位是 1 的概率就为：
误差的场景就是：元素不在集合中，但 k 次哈希到的位置上全是 1，这个概率为：
对于实际应用，我们的目标应该是使 错判率 p 最小。求最小值的过程略，直接上结论：当 k = (ln2)*(m/n) 时，误差率最小。以下是k取最优值时，各个参数之间的关系：
有了这些参数之间的关系表达式，就能方便的让我们计算最合适的参数。比如我们有 1000w 个黑产账号，需要以不高于 0.03%（万三——错误的的情况下识别出来。则需要的哈希函数个数为：-log2(0.0003) = 11.7 = 12，空间为：1.44 * 12 * 10000000 / 8 / 1024 / 1024 = 20MB
下面是一个网站，能帮忙我们快速计算各个参数：Bloom filter calculator
为什么布隆过滤器不支持删除
比特位上的1实际会对应多个元素，删除某元素后会影响其他元素。
比如 key a 对应比特位3、5，key b 对应5、10。若将a对应的3、5号位清空，则会影响b的判断。
计数布隆过滤器支持删除吗？不会误删吗？
支持；误删说明已经出现误差，冲突了
