0x00 前言
Bloom Filter 是由 Burton H. Bloom 在 1970 年提出的二进制向量数据结构，它具有很好的空间和时间效率，被用来检测一个元素是不是集合中的一个成员。
Bloom Filter 最初的论文发表在ACM，名为《Space/Time Trade-offs in Hash Coding with Allowable Errors》，感兴趣可以下载阅读。本篇主要分享 Bloom Filter 的基本原理、代码实现以及误判率的计算，看过 BitMap 那篇文章的童鞋再看这一篇会十分简单。
Bloom Filter 也就是常说的布隆过滤器，后面就统一称为 BF。
0x01 原理
BF 可以高效地表示集合数据，它使用长度为 m 的位数组来存储集合信息，同时使用 k 个相互独立的哈希函数将数据映射到位数组空间。
直接上图，根据图来大致梳理一下算法流程。
- 初始化一个长度为m的位数组，并将所有元素置为0；
- 对于集合
S={a1, a2,…,an}中的任一元素a，分别使用k个哈希函数对其计算： $w_i=hash_i(a)$，并将位数组中的第 $w_i$ 位置为1； - 对S中所有的成员执行同样的操作。
公众号
网友评论