Bloom 过滤器的优点

  1. 在数据量比较小的时候插入和查询的速度快
  2. 占用空间比较小

缺点：

  1. 数据量较大的时候，误报率和空间使用增高
  2. 不支持删除操作

Cuckoo 过滤器的优点：

  1. 支持删除操作
  2. 在大量数据时误报率较小

缺点：

  1. 空间占据大
  2. 实现比较复杂，插入和查询较慢

二 Bloom & Cuckoo性能比较

上表展示了bloom和cuckoo过滤器等其他一些常见过滤器的空间花费和是否支持删除操作，从中和以看出Cuckoo先比较Bloom要更花费空间。

上图展示了数据的容量和误报率的关系，可以看出两者在随着数据量的增大，其误报率也会随之增大，但是Cuckoo的误报率在达到上限时比Bloom的误差率要小。

上图显示了计数布隆过滤器和容量相同的Cuckoo过滤器的插入时间（。使用Cuckoo过滤器，我们注意到插入吞吐量增加高达85％，因为它填充高达80％的容量，而计数Bloom过滤器的插入吞吐量在此范围内保持相对稳定。在图中，我们进一步注意到Cuckoo滤波器在整个范围内比计数Bloom滤波器快约3倍，尽管Cuckoo滤波器的插入吞吐量显着增加。虽然这种差异在这里很重要，但可以对Bloom过滤器进行优化，以便为Cuckoo过滤器提供类似的插入速度。在这里，我们试图强调在Cuckoo过滤器填满时插入吞吐量的重大变化。

上图显示了几个常见过滤器的插入操作的性能，由于Cuckkoo的所需要的hash函数相比较Bloom的更少，通常是2个，所以在数据量小时，Cuckoo的冲突比较少，所以插入速度很快，但是当数据量增大时，冲突也随之增加，移动的操作也会增加，导致性能下降。

上图展示了常见的过滤器的查找性能，从上面的分析可以看出，由于Cuckoo的哈希函数更少所以在查询的性能上要好于Bloom。

## 三 总结：

两者各有其优缺点，所以一般用于不同的场合。Bloom过滤器及其变体在流媒体应用程序和其他成员测试至关重要的应用程序中证明非常有用，Cuckoo过滤器可以作为通常使用计数Bloom过滤器的场景的替代方案。

参考：

[1] B.Fan, David G. Andersen, M.Kaminskyy, Michael and D. Mitzenmacher. Cuckoo Filter: Practically Better Than Bloom.

[2] Julius. https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html