一、布隆过滤器

维基百科

  • 布隆过滤器(Bloom Filter)是1970年由布隆提出的。
  • 实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
  • 优点是不需要存储 key,节省空间,空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

原理概念

  • 如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。
  • 链表、树、散列表(哈希表)等等数据结构都是这种思路,但是随着集合中元素的增加,需要的存储空间越来越大;同时检索速度也越来越慢,检索时间复杂度分别是O(n)、O(log n)、O(1)。
  • 布隆过滤器的原理是,当一个元素被加入集合时,通过 K 个散列函数将这个元素映射成一个位数组(Bit array)中的 K 个点,把它们置为 1 。检索时,只要看看这些点是不是都是1就知道元素是否在集合中;如果这些点有任何一个 0,则被检元素一定不在;如果都是1,则被检元素很可能在(之所以说“可能”是误差的存在)。

自我理解

  • 直观的说,Bloom 算法类似于一个 HashSet(通过哈希算法得出元素的哈希地址,通过对比哈希地址就可以确定两个对象是否为同一个地址),用来判断某个元素(key)是否在某个集合中。
  • 和一般的 HashSet 不同的是,Bloom Filter 算法无需存储 key 的值,对于每个 key,只需要 k 个比特位,每个存储一个标志,用来判断 key 是否在集合中。

二、算法解析

BloomFilter 流程

  • 首先需要 k 个 hash 函数,每个函数可以把 key 散列成为 1 个整数;
  • 初始化时,需要一个长度为 n 比特的数组,每个比特位初始化为 0;
  • 某个 key 加入集合时,用 k 个 hash 函数计算出 k 个散列值,并把数组中对应的比特位置为 1;
  • 判断某个 key 是否在集合时,用 k 个 hash 函数计算出 k 个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

哈希冲突

假设 Hash 函数是良好的,如果我们的位阵列长度为 m 个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法,就是使用多个 Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们都在说谎,不过直觉上判断这种事情的概率是比较低的。— 如上 BloomFilter 流程

  一个 Bloom Filter 是基于一个 m 位的位向量(b1,…bm),这些位向量的初始值为0。另外,还有一系列的hash函数(h1,…,hk),这些 hash 函数的值域属于1~m。

算法实现示意图

一个 bloom filter 插入 {x, y, z},并判断某个值 w 是否在该数据集:

解析:m=18,k=3;插入 x 是,三个 hash 函数分别得到蓝线对应的三个值,并将对应的位向量改为1,插入 y,z 时,类似的,分别将红线,紫线对应的位向量改为1。查找时,当查找 x 时,三个 hash 值对应的位向量都为1,因此判断 x 在此数据集中。y,z 也是如此。但是查找 w 时,w 有个 hash 值对应的位向量为0,因此可以判断不在此集合中。但是,假如 w 的最后那个 hash 值是1,这时就会认为 w 在此集合中,而事实上,w 可能不在此集合中,因此可能出现误报。显然的,插入数据越多,1的位数越多,误报的概率越大。

三、BloomFilter的应用

  • 黑名单:比如邮件黑名单过滤器,判断邮件地址是否在黑名单中。
  • 排序(仅限于 BitSet) 。
  • 网络爬虫:判断某个URL是否已经被爬取过。
  • K-V系统快速判断某个key是否存在:典型的例子有 Hbase,Hbase 的每个 Region 中都包含一个 BloomFilter,用于在查询时快速判断某个 key 在该 region 中是否存在,如果不存在,直接返回,节省掉后续的查询。
说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...