目录
形容
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（后续具体阐明）
很多人说，后端工程师是“添删改查”工程师，那么我也不能免俗，上面从“添删改查”角度来进行论述：
- 增加过程：首先，用k个hash function将它hash失去bloom filter中k个bit位，之后将这k个bit地位1。
- 查问过程：即判断它是否在汇合中，用k个hash function将它hash失去k个bit位。若这k bits全为1，则此元素在汇合中；若其中任一位不为1，则此元素比不在汇合中
- 删除过程：不容许remove元素，因为那样的话会把相应的k个bits地位为0，而其中很有可能有其余元素对应的位。因而remove会引入false negative，这是相对不被容许的。
- 批改过程：删除都不容许了，批改更不容许，读者自行脑补吧。
误判率计算和证实
上面低潮来了，用数学公式来进行推倒证实：假如布隆过滤器中的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的各个参数的错误率
总结
公式推完了，大家能够看看，外面的数学公式根本用到了指数函数 对数函数 微积分求导法令 概率论的常识，大家能够补充看下课本。
参考文章
- http://www.cs.jhu.edu/~fabian...
- http://pages.cs.wisc.edu/~cao...
自我介绍
集体介绍：杜宝坤，京东联邦学习从0到1构建者，率领团队构建了京东的联邦学习解决方案，实现了电商营销畛域反对超大规模的工业化联邦学习解决方案，反对超大规模样本PSI隐衷对齐、平安的树模型与神经网络模型等泛滥模型反对，并且实现了广告侧等业务畛域的落地，创始了新的业务增长点，产生了显著的业务经济效益。
集体喜爱钻研技术。基于从全链路思考与决策技术布局的考量，钻研的畛域比拟多，从架构、数据到算法与算法框架均有波及。欢送喜爱技术的同学和我交换，邮箱：baokun06@163.com