目录

形容

Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组很简洁地示意一个汇合，并能判断一个元素是否属于这个汇合。Bloom Filter 的这种高效是有肯定代价的：在判断一个元素是否属于某个汇合时，有可能会把不属于这个汇合的元素误认为属于这个汇合（false positive）。因而，Bloom Filter 不适宜那些“零谬误”的利用场合。而在能容忍低错误率的利用场合下，Bloom Filter 通过极少的谬误换取了存储空间的极大节俭。

最近正好用到 bloomfilter，所以查问了些材料，整顿如下，本文将从原理与数学公式等角度进行讲述，波及到根本高等函数、微积分与概率论的常识，相干的常识请各位自行获取，本文默认各个读者有肯定的数学根底。

算法形容

bloom filter 是一个有 m bits 的 bit array，每一个 bit 位都初始化为 0。并且定义有 k 个不同的 hash function，每个都以 uniform random distribution 将元素 hash 到 m 个不同地位中的一个。n 为要增加到 bloomfilter 外面的元素。p 为错误率。所以相干的参数为：m n k p（后续具体阐明）

很多人说，后端工程师是“添删改查”工程师，那么我也不能免俗，上面从“添删改查”角度来进行论述：

1. 增加过程：首先，用 k 个 hash function 将它 hash 失去 bloom filter 中 k 个 bit 位，之后将这 k 个 bit 地位 1。
2. 查问过程：即判断它是否在汇合中，用 k 个 hash function 将它 hash 失去 k 个 bit 位。若这 k bits 全为 1，则此元素在汇合中；若其中任一位不为 1，则此元素比不在汇合中
3. 删除过程：不容许 remove 元素，因为那样的话会把相应的 k 个 bits 地位为 0，而其中很有可能有其余元素对应的位。因而 remove 会引入 false negative，这是相对不被容许的。
4. 批改过程：删除都不容许了，批改更不容许，读者自行脑补吧。

误判率计算和证实

上面低潮来了，用数学公式来进行推倒证实：假如布隆过滤器中的 hash function 使每个元素都等概率地 hash 到 m 个 slot 中的任何一个，与其它元素被 hash 到哪个 slot 无关（独立性）。若 m 为 bit 数，则对某一特定 bit 位在一个元素由某特定 hash function 插入时没有被置位为 1 的概率为：

从上式中能够看出，当 m 增大或 n 减小时，都会使得误判率减小，这也合乎直觉。

当初计算对于给定的 m 和 n，k 为何值时能够使得误判率最低。设误判率为 k 的函数为：

这阐明了若想放弃某固定误判率不变，布隆过滤器的 bit 数 m 与被 add 的元素数 n 应该是线性同步减少的。

三 如何设计 bloomfilter

首先，须要确定须要 add 的元素的个数与心愿的误差率，这个是整个零碎须要输出的参数，其余的参数有零碎主动计算，并且建设 bloomfilter。

此概率为某 bit 位在插入 n 个元素后未被置位的概率。因而，想放弃错误率低，布隆过滤器的空间使用率需为 50%。

bloomfilter 的各个参数的错误率

总结

公式推完了，大家能够看看，外面的数学公式根本用到了指数函数 对数函数 微积分求导法令 概率论的常识，大家能够补充看下课本。

参考文章

1. http://www.cs.jhu.edu/~fabian…
2. http://pages.cs.wisc.edu/~cao…

自我介绍

集体介绍：杜宝坤，京东联邦学习从 0 到 1 构建者，率领团队构建了京东的联邦学习解决方案，实现了电商营销畛域反对超大规模的工业化联邦学习解决方案，反对超大规模样本 PSI 隐衷对齐、平安的树模型与神经网络模型等泛滥模型反对，并且实现了广告侧等业务畛域的落地，创始了新的业务增长点，产生了显著的业务经济效益。

集体喜爱钻研技术。基于从全链路思考与决策技术布局的考量，钻研的畛域比拟多，从架构、数据到算法与算法框架均有波及。欢送喜爱技术的同学和我交换，邮箱：baokun06@163.com