文档章节

BloomFilter 与 CuckooFilter

强子1985
 强子1985
发布于 2017/07/10 23:57
字数 1802
阅读 74
收藏 1

Bloom Filter 原理

Bloom Filter是一种空间效率很高的随机数据结构,它的原理是,当一个元素被加入集合时,通过K个相互独立的Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了;如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。

Bloom Filter的这种高效是有一定代价的,在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,并不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

 

假设要你写一个网络爬虫程序(web crawler)。由于网络间的链接错综复杂,爬虫在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道爬虫程序已经访问过那些URL。给一个URL,怎样知道爬虫程序是否已经访问过呢?稍微想想,就会有如下几种方案:

  1. 将访问过的URL保存到数据库。
  2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
  3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
  4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。

其中,方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了:

方法1:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?

方法2:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。

方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。

方法4:消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。Bloom Filter 与单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。

 

创建一个m位BitSet,先将所有位初始化为0,然后选择k个不同的哈希函数。第 i 个哈希函数对字符串str哈希的结果记为Hi(str),并且满足:

0 <= Hi(str) < m     (1<=i<=k) 

(1) 将字符串 str 映射到BitSet中的过程:分别计算H1(str),H2(str),…,Hk(str),然后在BitSet中将对应的位置1。

(2) 检查字符串str是否被BitSet记录过的过程:分别计算H1(str),H2(str),…,Hk(str),然后在BitSet中对应的位检查是否为1。若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1,则认为字符串str存在。注意:这里也可能存在误判,因为有可能该字符串的所有位都刚好是被其他字符串所对应,这种将该字符串划分错的情况称为false positive 。

 

(3) 删除字符串过程,字符串加入了就被不能删除了,因为删除会影响到其他字符串。

实在需要删除字符串的可以使用Counting Bloom Filter (CBF),这是一种基本Bloom Filter的变体,CBF将基本Bloom Filter每一个Bit改为一个计数器,这样就可以实现删除字符串的功能了。

 

Bloom Filter 参数选择

 

问题:m(bit-map位数), n(待处理的字符串个数), k(哈希函数个数)值,我们该如何取值呢?

 

当hash函数个数 k = (ln2) * (m/n) 时错误率最小。

在错误率不大于e的情况下,则m >= n*log2(1/e)*log2e 。

这里直接给出了结论,如果对上述公式推导过程感兴趣,可以参考这里

举个例子我们假设错误率为0.001,则此时m应大概是n的14倍。这样k大概是4个。 

 

 

 

Bloom Filter 应用

最后,总结下Bloom Filter 的优点:

  • 节约缓存空间(空值的映射),不再需要空值映射;
  • 减少数据库或缓存的请求次数;
  • 提升业务的处理效率以及业务隔离性。

缺点:

  • 存在误判的概率;
  • 传统的Bloom Filter不能作删除操作(可以使用CBF来支持删除功能)。

 

Bloom Filter 可以用来实现数据字典,进行数据的判重,或者集合求交集 。

 

 

 

Cuckoo 布谷鸟哈希

前面提到,Bloom Filter 可能存在误报,并且无法删除元素,而Cuckoo哈希就是解决这两个问题的。

Cuckoo的哈希函数是成对的(具体的实现可以根据需求设计),每一个元素都是两个,分别映射到两个位置,一个是记录的位置,另一个是备用位置,这个备用位置是处理碰撞时用的。

如下图,使用hashA 和hashB 计算对应key x的位置a和b :

  1. 当两个哈希位置有一个为空时,则插入该空位置;
  2. 当两个哈希位置均不为空时,随机选择两者之一的位置上key y 踢出,并计算踢出的key y在另一个哈希值对应的位置,若为空直接插入,不为空踢出原元素插入,再对被踢出的元素重新计算,重复该过程,直到有空位置为止。

 

 

Cockoo hashing 有两种变形:一种通过增加哈希函数进一步提高空间利用率;另一种是增加哈希表,每个哈希函数对应一个哈希表,每次选择多个张表中空余位置进行放置,三个哈希表可以达到80% 的空间利用率。

Cockoo hashing 的过程可能因为反复踢出无限循环下去,这时候就需要进行一次循环踢出的限制,超过限制则认为需要添加新的哈希函数。

 

 

 

 

 

 

 

 

 

 

 

参考文档:

http://blog.csdn.net/v_july_v/article/details/6685894/

http://blog.csdn.net/v_july_v/article/details/7382693

http://www.dbafree.net/?p=36

https://github.com/jaybaird/python-bloomfilter/blob/master/pybloom/pybloom.py

http://coolshell.cn/articles/17225.html

 

本文转载自:http://www.cnblogs.com/chenny7/p/4074250.html

共有 人打赏支持
强子1985

强子1985

粉丝 866
博文 1002
码字总数 681491
作品 8
南京
架构师
私信 提问
Hadoop计算:ansj分词+BloomFilter+ Hadoop计算用户文件属性的方案

如果你有很多TB的日志,里面有个字段是文件名,如何根据文件名来计算此人的属性,比如文件是综艺,还是韩剧? 1 确定文件种类 先来谈谈确定文件种类的方案,刚开始想到是根据文件名去搜索,后...

强子哥哥
2014/12/03
0
0
WebMagic 0.5.1 发布,Java 爬虫框架

此次更新主要包括Scheduler的一些改动,对于自己定制过Scheduler的用户,强烈推荐升级。 修复了RedisScheduler无法去重的BUG,感谢@codev777 仔细测试并发现问题。 #117 对Scheduler进行了重...

黄亿华
2014/05/03
2.8K
15
当内存是瓶颈时,HashSet的一个替代类

在菜谱抓取过程中,需要对已抓取的url进行去重,一开始使用的HashSet来去重,但占用内存较大。于是改用BloomFilter(goolge guava jar包中的一个工具类)来去重。 下面是对HashSet与BloomFilt...

zgw06629
2015/04/27
0
0
大数据过滤及判断算法 -- Bitmap / Bloomfilter

今天,有个同学向我咨询大数据的一些面试题,其中一类比较有代表性比如判断是否在集合内,比如10个url,判断一个url是否在集合内,还比如有个1~100万个连续无序数字,随机取出里面的N个,求这...

长平狐
2013/01/05
416
0
Guava库学习:Guava 零碎知识

这将是Guava库学习系列的最后一篇,但是仍然包含许多零零碎碎的知识。虽然不可能覆盖所有Guava涉及的知识,但我们会竭尽所能。本篇将会介绍一些Guava中有用的工具,并不需要再开一个系列。本...

Realfighter
2015/05/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Vue重要知识小结

vue sync修饰 (1)双向数据绑定,父子组件之间信息的交互 1⃣️在自组件中使用this.emmit('toFather'),子组件产生一个tofather事件,然后在父组件中通过@进行监听,那么可以实现通信过程 2⃣...

peakedness丶
42分钟前
1
0
1024我们的码农节-向自己致敬!

一、blog主有话要说 作为(真正)入赘程序届的第一年, 对明天的1024码农节有很多话想说.比如: 给各位辛苦大佬们讲几个咱们程序届段子 给自己立一个flag, 明年的1024争取少掉点甚至不掉头发! ...

Ala6
44分钟前
12
0
solr使用规范

0. 目的 规范solr设计、用法,避免bug,提高性能 1. 设计规范 solr的用途是查询,不是存储,建议查询结果尽量都为id主键,而后再拿该id主键到缓存或者db中再查询相关信息,例如:请勿将经销商...

andersChow
56分钟前
1
0
11-《深度拆解JVM》之Java对象的内存布局

一、问题引入 在 Java 程序中,我们拥有多种新建对象的方式。除了最为常见的 new 语句之外,我们还可以通过反射机制、Object.clone 方法、反序列化以及 Unsafe.allocateInstance 方法来新建对...

飞鱼说编程
今天
1
0
Windows Install Docker

win7、win8 win7、win8 等需要利用 docker toolbox 来安装,国内可以使用阿里云的镜像来下载,下载地址:http://mirrors.aliyun.com/docker-toolbox/windows/docker-toolbox/ docker toolbox...

linuxprobe16
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部