布隆过滤器：用很少的内存回答“见过吗”
这一集讲了什么
布隆过滤器用一排只有 0 和 1 的格子，加上几个哈希函数，回答“这个元素以前见过吗”。放入元素时点亮它对应的几个格子；查询时只要有一个格子是暗的，就可以百分之百确定没见过。
代价是可能误报：格子全亮了也只能说“可能见过”，但绝不会漏报。这一集带你看误报是怎么出现的，再自己拖动格子数 m 和哈希个数 k，找到内存和准确率之间的平衡点。
先修
- 哈希表：空间换时间 即将推出
现实里用在哪
- Cassandra 读数据前先问每个磁盘文件的布隆过滤器，“肯定没有”就直接跳过这个文件，省下大量磁盘读取。
- HBase 给每个存储文件配布隆过滤器，查一行数据时只去可能包含它的文件里找。
- RocksDB LSM 存储引擎在每层的文件里放布隆过滤器，让查不到的键几乎不碰磁盘。
接着看
- LSM 树：把随机写变成顺序写 即将推出
第 3 集
本集是《数据结构与算法》系列的第 3 集（计划共 13 集）。