江苏龙网

  1. 主页 > 生活百科 > >

什么是布隆过滤器？你学会了吗？

布隆过滤器

前言如果要判断一个元素是否在集合中 ， 一般的思路是保存集合中的所有元素 ， 然后通过比较来确定 。链表、树、哈希表（也叫哈希表、哈希表）等数据结构都是这种方式 ， 存储位置要么是磁盘 ， 要么是内存 。很多时候 ， 要么时间换空间 ， 要么空间换时间 。
【什么是布隆过滤器？你学会了吗？】在对响应时间要求比较严格的情况下 ， 如果我们有里面 ， 那么随着集合中元素数量的增加 ， 我们需要的存储空间越来越大 ， 检索时间也越来越长 ， 导致内存过多开销和时间效率变低 。
这时候需要考虑的问题是 ， 在数据量比较大的情况下 ， 既能满足时间要求 ， 又能满足空间要求 ， 所以我们需要一种时间和空间消耗都比较小的数据结构和算法 。布隆过滤器是一种解决方案 。
什么是布隆过滤器？Bloom Filter, 布隆过滤器由 Bloom于 1970 年提出 。它实际上是一个长二进制向量和一系列随机映射函数, 布隆过滤器可用于检索元素是否在集合中 。其优点是空间效率和查询时间远超一般算法 ， 缺点是存在一定的误识别率和删除难度 。根据它的特性 ， 应用场景有如下：

  • 爬虫过滤 。
  • 邮箱垃圾邮件过滤 。
  • 黑名单过滤 。
  • 大数据去重 。
  • 防止缓存穿透 。
布隆过滤器原理布隆过滤器的原理是当一个元素加入到集合中时 ， 通过K个哈希函数将该元素映射到一个位数组中的K个点 ， 并将它们置为1 。检索时 ， 我们只需要看这些点是否都为1 ， 就可以（大概）知道它是否存在于集合中 。如果这些点中的任何一个有0 ， 则检查的元素一定不存在 。如果它们都是1 ， 则被选中的元素很可能在那里 。
Bloom Filter与单一哈希函数Bit-Map的区别在于 ， Bloom Filter使用k个哈希函数 ， 每个字符串对应k个bits ， 从而降低碰撞概率 。
什么是布隆过滤器？你学会了吗？

文章插图
由于Bloom filter只存储0和1而不存储具体值 ， 所以在一些机密场合具有先天优势 。位图的每一位都是一个位 ， 所以通过位图有10亿个位置 ， 位图的大小为0.12G ， 插入和查询的时间复杂度为O(k),k是哈希函数的个数 。
布隆过滤器的问题布隆过滤器之所以能够在时间和空间上取得比较高的效率 ， 是因为它牺牲了判断的准确性和删除的便利性 。
  1. 判断错误
有可能要找的元素不在容器中 ， 但是散列后得到的k个位置都是1 。如果布隆过滤器中存储了黑名单 ， 则可以通过创建白名单来存储可能被误判的元素 。
对于这个问题 ， 可以通过增加位图数组的大小（位图数组越大 ， 占用的内存越大）和减少哈希冲突来解决 。但缺点是会增加占用的内存空间 。
另一种解决方案是增加散列函数的数量并减少散列冲突 。如果同一个键值等于一个函数 ， 经过两个或多个哈希函数得到相等结果的概率自然会降低 。然而 ， 这会导致计算效率的降低 ， 因为时间复杂度退化为O(hash times) 。
  1. 难以去除
放置在容器中的元素映射到位数组的 k 个位置中的 1 。删除的时候不能简单的直接设置为0 ， 这样可能会影响其他元素的判断 。你可以使用??Counting Bloom Filter??来解决这个问题 。
JAVA中如何使用布隆过滤器google的guava就提供了这样的API.
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>22.0</version></dependency>编写测试代码
import com.google.common.base.Charsets;import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels; public class GuavaBloomFilter {public static void main(String[] args) {int total = 1000000;// default false positive ratefpp0.03// fpp:There will always be a false positive rate in a Bloom filter// Because hash collisions are impossible to avoid 100%.// Bloom filter calls this misjudgment rate false positive probability ， abbreviated as fppBloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);// Initialize the total bar data into the filterfor (int i = 0; i < total; i++) {bf.put("" + i);}// Determine whether the value exists in the filterint count = 0;for (int i = 0; i < total + 10000; i++) {if (bf.mightContain("" + i)) {count++;}}System.out.println("Matched quantity " + count);// Specified misjudgment rate: 1/10,000 to improve matching accuracyBloomFilter<CharSequence> bfWithFpp = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);for (int i = 0; i < total; i++) {bfWithFpp.put("" + i);}int countFpp = 0;for (int i = 0; i < total + 10000; i++) {if (bfWithFpp.mightContain("" + i)) {countFpp++;}}//The smaller the value of the false positive rate fpp// the higher the matching accuracy.// When the value of the false positive rate fpp is reduced// the storage space required is also larger// Therefore, in actual use,// a trade-off needs to be made between the false positive rate and the storage space.System.out.println("The specified false positive rate has matched the number " + countFpp);// (1000001 - 1000000)/(1000000 + 10000) * 100 ≈ 0.0001}}


推荐阅读


上一篇：三分钟轻松搞懂 HashMap 死循环问题！

下一篇：没有了