布隆过滤器(Bloom Filter)
bloom 算法相似一个 hash set, 用来判断某个元素是否在某个汇合中. bloom 不须要存储元素的值, 而是对于每个元素用 k 个比特位来存储其标记, 用来判断元素是否在汇合中.
布隆过滤器算法:
1. 首先须要 k 个 hash 函数, 每个函数能够把元素散列成 1 个整数
2. 初始化时, 须要一个长度为 n 比特的数组, 每个比特位初始化为 0
3. 当一个元素退出汇合时, 用 k 个 hash 函数计算出 k 个散列值, 并把比特数组中对应的比特地位为 1
4. 判断元素是否在汇合中时, 只须要查问比特数组中对应的 k 个比特位, 如果所有的比特位都为 1, 示意汇合中存在这个元素
介绍
布隆过滤器 (Bloom Filter) 是由布隆在 1970 年提出的. 它由一个很长的 二进制向量 和一系列 随机映射函数 组成, 布隆过滤器能够 检索一个元素是否在一个汇合中.
长处:相比于其余数据结构, 布隆过滤器在工夫和空间方面都有微小的劣势 (都是常数)
毛病:有肯定的 误识别率 (Bloom Filter 报告元素存在于汇合中, 但实际上并不存在) 和删除艰难 , 但 不会谬误辨认 ( 如果元素的确不存在于汇合中, Bloom Filter 不会报告该元素存在于汇合中)
布隆过滤器用例
- Google 驰名的分布式数据库 Bigtable 应用了布隆过滤器来查找不存在的行或列，以缩小磁盘查找的 IO 次数
- Google Chrome 浏览器应用了布隆过滤器减速平安浏览服务
- 辨认垃圾邮件，只有是邮箱在黑名单中的邮件，就辨认为垃圾邮件。假如黑名单的数量是数以亿计的，寄存起来就是十分消耗存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。
- 在很多的 Key-Value 零碎中也应用了布隆过滤器来放慢查问服务, 如 HBase, 一般而言，Value 保留在磁盘中, 拜访磁盘须要破费大量工夫, 然而应用布隆过滤器能够疾速判断某个 Key 对应的 Value 是否存在, 因而能够防止很多不必要的磁盘 IO 操作, 只是引入布隆过滤器