本质：一个空的2进制数组（初始全为0，只存0和1）
一个key，经过k个hash函数运算后，得到k个值，将2进制数组对应下标的位置置为1。
将key同样进行k个hash，去2进制数组比对对应下标位置的值
不能删
缓存穿透：key对应的数据在数据源并不存在，每次针对此key的请求从缓存获取不到，请求都会到数据源，从而可能压垮数据源。
解决办法：将数据源的key是否存在的信息存储到布隆过滤器中，如果布隆过滤器判定数据不存在，则不再请求数据源。
基本的布谷鸟过滤器由两个并不独立的哈希函数构成。
基本单位为条目，每个条目存储一个指纹。
指纹指的是使用一个哈希函数生成的n位比特位，n的具体大小由所能接受的误判率来设置。一般n=8
布谷鸟哈希表由一个桶数组构成，每个桶可以有多个条目，即每个桶中有多个存放指纹的位置。
先进行一次hash，得出应当插入位置和应当插入的值（指纹）。
如果这个桶（桶内的m个位置均被占用）插入失败，会重新计算(指纹哈希与第一个索引异或)，查看第二个桶能否插入。
若第二个桶插入失败，则会随机在两个桶中挑选一个桶，将其中的一个值标记为旧值，用新值覆盖旧值，旧值会在重复上面的步骤进行插入。
如果数组过小，会发生循环挤兑的情况。
如果超过最大挤兑次数，进行扩容，重新计算每个指纹的位置。
删除后再添加新指纹。
| 布隆过滤器 | 布谷鸟过滤器 | |
|---|---|---|
| 插入 | k个hash函数 | 2个hash函数 |
| 删除 | 不能删 | 可以删 |
| 更新 | 不能更新 | 删除后再添加 |
| 查询 | 有误判率 | 有误判率 |
| 优点 | 安全、节省空间 | 查询效率高、支持删除、更节省空间 |
| 缺点 | 有误判率、无法删除 | 插入性能差、插入重复元素有上限、空间大小为2的指数、删除不完美 |