布隆过滤器(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操作, 只是引入布隆过滤器