布隆过滤器之误识别率FPP公式的推导

在《什么是布隆过滤器(Bloom Filter)?》一文中,多次提到了误识别率(FPP,false positive probabilistic)。

那么误识别率到底是多大,应该如何计算呢?

假设布隆过滤器大小为m比特,存储了n个元素,使用k次散列函数来计算元素的存储位置。 … [阅读文章]

什么是布隆过滤器(Bloom Filter)?

在日常工作中,有一个比较常见的需求,就是需要判断一个元素是否在集合中。

例如以下场景:

给定一个IP黑名单库,检查指定IP是否在黑名单中? 在接收邮件的时候,判断一个邮箱地址是否为垃圾邮件? 在文字处理软件中,检查一个英文单词是否拼写正确?

遇到这种问题,通常直觉会告诉我们,应该使用集合这种数据结构来实现。例如,先将IP黑名单库的所有IP全部存储到一个集合中,然后再拿指定的IP到该集合中检查是否存在,如果存在则说明该IP命中黑名单。 … [阅读文章]