布隆过滤器（Bloom Filter）、布谷鸟过滤器（Cuckoo Filter)、商过滤器（quotient filter）(持续更新~~~~)

位图

在讨论布隆过滤器之前，先看一下位图是什么。

首先考虑一个问题场景

假如需要过滤某些不安全网页，现有100亿个黑名单页面，每个网页的URL最多占用64字节。现要设计一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上。

最直观的想法必然是使用一个集合或者说数据结构来存放黑名单URL，比如查找树、Set、map，但是无论哪种，不可避免的是我们需要存储原始的URL值，但是我们都知道URL并不是一个很短的字符串，动辄十几/几十字节，假设一个URL有30字节那么100亿URL所占内存就是十几G，所以每次判断是否存在于黑名单中，就要占用很大的内存开销。

但是，我们的需求仅仅是该URL是否存在，可以不需要具体的URL，所以可以转化为Ture or False 这个问题，可以使用位图（BitMap）算法，位图顾名思义就是，每个map值都使用1bit，这样大大降低了内存开销，具体做法是，我们使用一个Hash函数将URL映射到大小为n的bit数组中，并置相应位置为True

这样我们可以在尽可能低的内存开销下，实现O（1）时间的判断URL是否存在黑名单中。

存在的问题：即使采取再好的哈希函数，都会出现哈希冲突的情况，在查询阶段出现哈希冲突意味着查询错误，会返回一个错误的结果，而想尽可能的降低哈希冲突，我们需要位图大小比黑名单中URL数量大的多，我们考虑随机哈希的情况下，查询碰撞的概率是：黑名单URL数量/位图大小。所以要想查询准确率高，又带来了更高的内存开销，而可以有效改善这种情况的一种数据结构叫做过滤器（Filter）。

布隆过滤器（Bloom Filter）

什么是布隆过滤器

  布隆过滤器是一种节省空间的概率 数据结构，由Burton Howard Bloom在 1970 年构思，用于测试元素是否是集合的成员。误报匹配是可能的，但漏报不是——换句话说，查询返回“可能在集合中”或“绝对不在集合中”。元素可以添加到集合中，但不能删除（尽管这可以通过计数布隆过滤器变体来解决）；添加的项目越多，误报的概率就越大。

  考虑位图情况出现的问题：在有限的比特数组大小下，碰撞概率会很高，布隆过滤器解改善了这个问题，具体的，它使用多个Hash函数对数据进行哈希操作（如下图使用了两个hash函数），这样得出多个位置为True，相比位图它在有限的空间内，尽可能的降低了查询失败的可能，这一点可以从信息熵的角度来看，每一个位置所包含的信息更加多了，所以比起位图来说，布隆过滤器对空间的利用率也变大了，当然这一点也会带来别的坏处下面会说到。

上面谈到，布隆过滤器每个位置不再标识一条数据，可能标识多条数据，因而对于bit数组中的某个位置来讲，它的值信息熵更大了，但是既然一个位置可以标识多条数据，正所谓牵一发而动全身，所以布隆过滤器也就存在的一个问题，无法对黑名单进行删除操作，比如上述的例子，下标为箭头指向同一个位置是两条数据经过不同的哈希运算后得到了同样的结果，假如要删除一条数据必然影响其他数据的查询结果，造成更高的误判率。

误判率

  布隆过滤器的误判率也可以称之为假阳性（false positive）的概率，比如来一条URL查询是否在黑名单中，结果其对应的哈希结果已经被其他一个或者多个URL置1，那么此时就出现了查询错误的情况。所以布隆过滤器只适合有内存开销限制、并且允许出现错误率的情况。误判率推导

使用（以Java为例）

使用Google 开源的 Guava 中自带的布隆过滤器，这里简单介绍一下它的使用，首先需要引入依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.0-jre</version>
</dependency>
1
2
3
4
5

实际应用

海量数据下，通过设计正确适用的布隆过滤器以很低的错误率带来了几十倍的内存开销降低，其应用范围也很广，比如

• 识别恶意邮箱地址。
• URL黑名单、白名单，比如Chrome浏览器就是使用了一个布隆过滤器识别恶意链接。
• 解决缓存穿透问题，缓存穿透指查询一个不存在的数据，这时候缓存中不存在，就会不断的查询数据库，造成不必要的IO，而且有人如果恶意使用不存在的key也可以对数据库进行攻击。
• 果蝇…通过改进的布隆过滤器来检测新鲜气味。（混入一个奇怪的东西）
• 谷歌Bigtable、Apache HBase、Apache Cassandra和PostgreSQL使用布隆过滤器来减少对不存在的行或列的磁盘查找。
• …

布谷鸟过滤器（Cuckoo Filter)

布谷鸟哈希

最原始的布谷鸟哈希方法是使用两个哈希函数对一个key进行哈希，得到桶中的两个位置，此时

• 如果两个位置都为为空则将key随机存入其中一个位置
• 如果只有一个位置为空则存入为空的位置
• 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置

当然假如存在绝对的空间不足，那老是踢出也不是办法，所以一般会设置一个踢出阈值，如果在某次插入行为过程中连续踢出超过阈值，则进行扩容。

布谷鸟过滤器插入、查找、删除

  布谷鸟过滤器是一种节省空间的概率 数据结构，用于测试元素是否是集合的成员，就像布隆过滤器一样。误报匹配是可能的，但漏报不是——换句话说，查询返回“可能在集合中”或“绝对不在集合中”。布谷鸟过滤器还可以删除现有的项目，布隆过滤器不支持。此外，对于存储许多项目并以适度低误报率为目标的应用程序，布谷鸟过滤器可以实现比空间优化的布隆过滤器更低的空间开销。

插入：
布谷鸟过滤器的插入是重点，与朴素的布谷鸟哈希不同，布谷鸟过滤器采取了两个并不独立的哈希函数，具体的
$$i_1=hash(x)$$$$i_2=i_1\oplus hash(f)$$
$i1,i2$即计算出来两个桶的索引，其中第一个桶的索引是通过某个哈希函数计算出来，第二个是使用第一个索引和指纹的哈希做了一个异或操作，进行异或操作的好处是，因为异或操作的特性：同为0不同为1，且0和任何数异或是这个数的本身。那么$i1$也可以通过$i2$和指纹异或来计算。 换句话说，在桶中迁走一个键，我们直接用当前桶的索引i

和存储在桶中的指纹计算它的备用桶。

具体的指纹是通过哈希函数取一定量的比特位
$$f=fingerprint(x)$$

查找：
布谷鸟过滤器的查找过程很简单，给定一个项$x$，算法首先根据上述插入公式，计算$x$的指纹和两个候选桶。然后读取这两个桶：如果两个桶中的任何现有指纹匹配，则布谷鸟过滤器返回true，否则过滤器返回false。此时，只要不发生桶溢出，就可以确保没有假阴性。

删除：
标准布隆过滤器不能删除，因此删除单个项需要重建整个过滤器，而计数布隆过滤器需要更多的空间。布谷鸟过滤器就像计数布隆过滤器，可以通过从哈希表删除相应的指纹删除插入的项，其他具有类似删除过程的过滤器比布谷鸟过滤器更复杂。

具体删除的过程也很简单，检查给定项的两个候选桶；如果任何桶中的指纹匹配，则从该桶中删除匹配指纹的一份副本。

布谷鸟过滤器不足

• 删除不完美，存在误删的概率。删除的时候知识删除了一份指纹副本，并不能确定此指纹副本是要删除的key的指纹。同时这个问题也导致了假阳性的情况。
• 插入复杂度比较高。随着插入元素的增多，复杂度会越来越高，因为存在桶满，踢出的操作，所以需要重新计算，但综合来讲复杂度还是常数级别。
• 存储空间的大小必须为2的指数的限制让空间效率打了折扣。
• 同一个元素最多插入kb次，（k指哈希函数的个数，b指的桶中能装指纹的个数也可以说是桶的尺寸大小）如果布谷鸟过滤器支持删除，则必须存储同一项的多个副本。 插入同一项kb+1次将导致插入失败。 这类似于计数布隆过滤器，其中重复插入会导致计数器溢出

商过滤器（quotient filter）

指纹：$f=hash(x)$

商：$f_q=f/2^r$

余数：$f_r=fmod{2}^r$

三元组表示意义：

1. For each slot $i$, we maintain an is-occupied bit to quickly check whether there exists a fingerprint $f\in F$ such that $f_q=i$.

2. For a remainder $f_r$ stored in slot $i$, we keep track of whether $f_r$ belongs to the same run as the remainder stored in slot $i-1$ with an is-continuation bit.

3. For a remainder $f_r$ stored in slot $i$, we record whether $f_r$ belongs to bucket $i$ (i.e., $f_q=i$) with an is-shifted bit.

文章参考链接

1. 布隆过滤器
2. 布谷鸟过滤器
3. Quotient filter
4. 论文：Don’t Thrash: How to Cache Your Hash on Flash（第三节讲述）