经典论文解读——布隆过滤器
Source :
mp.weixin.qq.com
Author :
腾讯程序员
相信大家对布隆过滤器（Bloom Filter，BF）都不陌生，就算没用过也听过。布隆过滤器是一种具有空间优势的概率数据结构，用于回答一个元素是否存在于一个集合中这样的问题，但是可能会出现误判——即一个元素不在集合但被认为在集合中。 布隆过滤器可用于避免缓存穿透、海量数据快速查询过滤之类的场景。但是，大家真的了 BF 吗？BF 有哪些参数？BF 支持删除吗？BF 的哈希函数怎么选？还有其他类型的 BF 吗？等等...... 本文将从论文着手，从 BF 的起源开始，介绍初始的 BF，介绍 BF 的概率计算过程。接着介绍几个 BF 的变种：包括可以支持删除的(Count Bloom Filter, CBF)；在 CBF 的基础上能进一步节省空间的(dlCBF)；支持多个集合的(Spatial Bloom Filter, SBF)和支持动态扩容的(Scalable Bloom Filter)。最后介绍一些关于 BF 的疑问，并且结合部分 Golang 组件源码分析，将 BF 的理论带入设计实践。
