BloomFilter详解（布隆过滤器）

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

现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：

这说明了若想保持某固定误判率不变，布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。

三 如何设计bloomfilter

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

bloomfilter的各个参数的错误率

公式推完了，大家可以看看，里面的数学公式基本用到了指数函数 对数函数 微积分求导法则 概率论的知识，大家可以补充看下课本。

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

个人喜欢研究技术。基于从全链路思考与决策技术规划的考量，研究的领域比较多，从架构、数据到算法与算法框架均有涉及。欢迎喜欢技术的同学和我交流，邮箱： baokun06@163com

---