乐趣区

关于布隆过滤器:布隆过滤器BoomFilter学习

jiezi

一、什么是布隆过滤器（BoomFilter）

Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组很简洁地示意一个汇合，并能判断一个元素是否属于这个汇合。它实际上是一个很长的二进制向量和一系列随机映射函数。

特点总结为如下：

  • 空间效率高的概率型数据结构，用来查看一个元素是否在一个汇合中。
  • 对于一个元素检测是否存在的调用，BloomFilter 会通知调用者两个后果之一：可能存在或者肯定不存在。

二、应用场景

  1. 解决缓存穿透
    咱们常常会把一部分数据放在 Redis 等缓存，比方产品详情。这样有查问申请进来，咱们能够依据产品 Id 间接去缓存中取数据，而不必读取数据库，这是晋升性能最简略，最广泛，也是最无效的做法。个别的查问申请流程是这样的：先查缓存，有缓存的话间接返回，如果缓存中没有，再去数据库查问，而后再把数据库取出来的数据放入缓存，所有看起来很美妙。然而如果当初有大量申请进来，而且都在申请一个不存在的产品 Id，会产生什么？既然产品 Id 都不存在，那么必定没有缓存，没有缓存，那么大量的申请都怼到数据库，数据库的压力一下子就上来了，还有可能把数据库打死。
    尽管有很多方法都能够解决这问题，然而咱们的配角是“布隆过滤器”，没错，“布隆过滤器”就能够解决（缓解）缓存穿透问题。至于为什么说是“缓解”，看上来你就明确了。
  1. 大量数据，判断给定的是否在其中
    当初有大量的数据，而这些数据的大小曾经远远超出了服务器的内存，当初再给你一个数据，如何判断给你的数据在不在其中。如果服务器的内存足够大，那么用 HashMap 是一个不错的解决方案，实践上的工夫复杂度能够达到 O(1)，然而当初数据的大小曾经远远超出了服务器的内存，所以无奈应用 HashMap，这个时候就能够应用“布隆过滤器”来解决这个问题。然而还是同样的，会有肯定的“误判率”。
  1. 进行垃圾邮件过滤(垃圾数据过滤)
  1. 网页爬虫对 URL 的去重，防止爬取雷同的 URL 地址

三、实现原理

布隆过滤器的外围实现是一个超大的位数组和几个哈希函数。假如位数组的长度为 m，哈希函数的个数为 k。

以上图为例，具体的操做流程：假如汇合外面有 3 个元素 {x, y, z}，哈希函数的个数为 3。首先将位数组进行初始化，将外面每一个位都设置位 0。对于汇合外面的每个元素，将元素顺次通过 3 个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组下面的一个点，而后将位数组对应的地位标记为 1。查问 W 元素是否存在汇合中的时候，一样的办法将 W 通过哈希映射到位数组上的 3 个点。若是 3 个点的其中有一个点不为 1，则可能判断该元素必然不存在汇合中。反之，若是 3 个点都为 1，则该元素可能存在汇合中。留神：此处不能判断该元素是否必然存在汇合中，可能存在必然的误判率。可能从图中可能看到：假如某个元素通过映射对应下标为 四、五、6 这 3 个点。尽管这 3 个点都为 1，可是很显著这 3 个点是不一样元素通过哈希取得的地位，所以这种情况阐明元素尽管不在汇合中，也可能对应的都是 1，这是误判率存在的原因。

劣势
相比于其它的数据结构，布隆过滤器在空间和工夫方面都有微小的长处。布隆过滤器存储空间和插入 / 查问工夫都是常数。另外，Hash 函数相互之间没有关系，不便由硬件并行实现。布隆过滤器不须要存储元素本人，在某些对窃密要求很是严格的场合有长处。
布隆过滤器可能示意选集，其它任何数据结构都不能。

毛病
可是布隆过滤器的毛病和劣势同样显著。误算率（False Positive）是其中之一。随着存入的元素数量增长，误算率随之增长（误判补救办法是：再创立一个小的白名单，存储那些可能被误判的信息）。可是若是元素数量太少，则应用散列表足矣。
另外，通常情况下不能从布隆过滤器中删除元素。咱们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可能了。然而要保障平安的删除元素并不是如此简略。首先咱们必须保障删除的元素确实在布隆过滤器外面. 这一点单凭这个过滤器是没法保障的。另外计数器回绕也会造成问题。

四、举荐应用 Guava 的布隆过滤器

Maven：

<dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>22</version>
</dependency>

建设 BloomFilter 对象，须要传入 Funnel 对象，预估的元素个数，误判率。

BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 1000,0.01);

应用 put 办法增加元素：

filter.put("test");

应用 mightContain 办法判断元素是否存在：

filter.mightContain("test");
退出移动版