背景
特征 or 全部
在实际需求中，往往存在类似需求：
- 黑白名单；例如手机号、网站等，需要过滤掉在黑名单中的数据，或者放行在白名单中的数据
- 推荐去重；首页新闻、视频等资源已经给用户推荐过的不进行重复推送
- 缓存穿透；保证缓存层能正常工作，不被特殊请求大量造成缓存穿透
最容易想到的，就是通过一个集合例如 Map、List 等结构将数据存储起来，判断是否存在于集合中
这样相当于把所有的数据都进行了一遍存储，如果需要的只是过滤功能，而不需要将数据全部存储下来，只需要存储数据的特征值，就可以节省大量的空间
所以出现了布隆过滤器等概率型结构（probabilistic data structure），可以在使用很少空间的情况下对数据进行过滤操作，当然通过特征值进行存储可能会有以下问题：
- 误判率
- 扩缩容依然需要数据全集（数据量不匹配会导致空间浪费或误判率上升）
- 删除操作难以实现
需要在技术和业务两方面进行取舍
布隆
布隆过滤器（bloom filter）由一串很长的二进制向量组成（位图 bitmap），可以将其看成一个二进制数组
当一个元素进入时，不是存储该元素本身，而是通过多个哈希算法，计算出该元素的多个下标，随后在位图中将对应的下标打上标记（bit 位置为 1），当需要判断是否存在某个元素时，也是进行哈希后，判断其需要的下标是否全为 1
可以看出，布隆过滤器带有一定的误判率，如果很多元素的下标正好复合了某一个元素的位置，那么该元素就会被误判存在：
- 说存在但不一定存在
- 说不存在一定不存在
图示模拟流程：https://www.jasondavies.com/bloomfilter/
参数选择
也可以看出布隆过滤器的误判率和以下参数相关：
- 过滤器中位图的位数
- 哈希算法的数量和质量
Bloom filter calculator (hur.st) 可以进行布隆过滤器参数的预估
| 参数值 | 含义 | 公式 |
|---|---|---|
| n | 过滤器中的元素数量 | n = ceil(m / (-k / log(1 - exp(log(p) / k)))) |
| p | 误判率 | p = pow(1 - exp(-k / (m / n)), k) |
| m | 过滤器使用的空间大小 | m = ceil((n * log(p)) / log(1 / pow(2, log(2)))); |
| k | 哈希算法数量 | k = round((m / n) * log(2)); |
无法删除
布隆过滤器是无法删除元素的，因为一旦存储特征后，删除会导致连带其他元素的标记一起删除
为了能让布隆过滤器支持删除操作，衍生出了变体结构，计数布隆过滤器（counting bloom filter）
实际应用
Now 直播发现页短视频瀑布流优化 - 开发者头条 (toutiao.io)
计数布隆
使用一个 counter 数组来替代之前的位图，在进行标记时可以记录一共标记了多少次，显而易见空间占用会扩大不少
在进行判断时 counter > 0 即表示了之前的
index == 1 操作
计数器也无法避免误删，只是能大幅度降低误删概率
布谷鸟
布谷鸟过滤器是布隆过滤器的升级，有如下优势：
- 支持动态的新增和删除元素
- 提供了比传统布隆过滤器更高的查找性能，即使在接近满空间的情况下（访问内存次数低）
- 要求一定误判率下，空间占用一般更小
布谷鸟 hash
当发现鸟蛋占用了自己的位置时，就把它推走
假设有两个 hash 表，记为 T1 和 T2
同时有两套 hash 算法，记为 H1 和 H2
添加元素流程如下：
- 根据 H1 计算其在 T1 的位置下标
- 如果该位置没有标记则进行标记，如果标记了则继续
- 根据 H2 计算其在 T2 的位置下标
- 如果该位置没有标记则进行标记，如果标记了则说明所有位置都已经被占用，随机踢出 T1 或者 T2 上该下标的元素，将自己放入下标
- 被踢出的元素重复上述流程查找自己的位置
- 经过
MaxLoop阈值后还存在元素没有合适的位置，则元素添加失败，说明需要进行扩容了
图示模拟流程：http://www.lkozma.net/cuckoo_hashing_visualization/
过滤器的 hash
布谷鸟过滤器的 hash 是对布谷鸟 hash 的改进
布谷鸟 hash 中，哈希表存储的是元素的原始值 x，下标 p1 p2 的计算公式为
p1 = hash1(x) % Lp2 = hash2(x) % L
而布谷鸟过滤器对于下标的计算为：
h1(x) = hash(x)h2(x) = h1(x) ⊕ hash(x's fingerprint)
我们可以看到，计算 h2（位置 2）时，对 x 的 fingerprint 进行了一个 hash 计算，公式中的异或操作获得了一个重要的特性：位置 h2 可以通过位置 h1 和 h1 中存储的 fingerprint 计算出来，即当元素被踢出时，根据当前位置和元素的指纹，就可以得到元素的下一个位置
异或与对偶
由 h2 的计算公式
h2(x) = h1(x) ⊕ hash(x's fingerprint)，两个位置具有对偶性
只要保证 hash(x's fingerprint) !=0，那么就可以确保
h2 != h1，也就可以确保，不会出现自己踢自己的死循环问题
为什么需要对指纹进行哈希运算呢？因为如果指纹的长度是 8 bit，那么异或操作只会改变当前位置 h1(x) 的低 8 位，高位不会改变，就算低 8 位完全不一样，最后计算出来的位置最远也只有 256 位，为了散列更充分，所以对指纹先进行一次哈希操作
指纹
指纹其实就是元数据的特征值，进行哈希后取的固定 n 个 bit 位
空间利用率
由于指纹是对数据进行哈希运算后固定的 bit 位，所以必然会出现误判的情况
在完美的情况下，也就是没有发生哈希冲突之前，它的空间利用率最高只有 50%
如果对数组进行展开，当一个位置可以存放多个数据时，空间利用率会提升；如果一个下标可以放 2、4、8 个元素的时候，空间利用率就会飙升到 84%、95%、98%
删除的限制
如果需要布谷鸟过滤器支持删除，它必须知道一个数据插入过多少次（否则也会误删）
并且不能让同一个数据插入 kb+1 次；个人认为如果插入超过了
kb+1 次，就会导致插入一定失败
总结
布谷鸟的优缺点：
优点：
- 访问内存次数低
- Hash 函数计算简单
- 支持删除操作
缺点：
- 内存空间不联系，CPU 消耗大
- 容易出现装填循环问题，空间占用越多碰撞越多，插入效率越低
- 查询误判率
- 删除操作限制多，会影响插入性能和误删除
参考
https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
布隆，牛逼！布谷鸟，牛逼！ - 知乎 (zhihu.com)