漫画:什么是布隆算法?

漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



两周之前——



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



爬虫的原理就不细说了,无非是通过种子URL来顺藤摸瓜,爬取出网站关联的所有的子网页,存入自己的网页库当中。



漫画:什么是布隆算法?



但是,这其中涉及到一个小小的问题……



漫画:什么是布隆算法?



漫画:什么是布隆算法?



URL去重方案第一版:HashSet


创建一个HashSet集合,把每一个URL字符串作为HashSet的key插入到集合当中,利用HashSet的Key唯一性来对URL做去重。



漫画:什么是布隆算法?



这个方案看似没毛病,但是经过几轮压测之后……



漫画:什么是布隆算法?



每一个URL按照20字节来算,一亿个URL就是20亿字节,也就是大约占了1.8G以上的空间。这么大的HashSet集合显然是不可取的。


于是小灰又思考了一番……



漫画:什么是布隆算法?



URL去重方案第二版:Bitmap


Bitmap是一种节省空间的数据结构,不太了解的朋友可以看看往期的相关文章:


漫画:Bitmap算法 整合版


具体怎么做呢?获取每一个URL的HashCode,根据HashCode的值来插入到Bitmap的对应位置。如果要插入位置的值已经是1,说明该URL已重复。


漫画:什么是布隆算法?



使用Bitmap以后,每一个Url只占了1个Bit,一亿个Url占约12MB。假设整个Bitmap的空隙比较多,额外空间占90%,总空间也不过是120MB,相比HashSet来说大大节省了内存空间。


这个方案貌似好了很多,可是……



漫画:什么是布隆算法?



String的Hashcode方法虽然尽可能做到均匀分布,但仍然免不了会有冲突的情况。HashCode的冲突意味着什么呢?意味着两个原本并不相同的Url被误判为重复Url。



漫画:什么是布隆算法?



———————————————



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



听起来有点绕,我们来详细描述一下:


1.把第一个URL按照三种Hash算法,分别生成三个不同的Hash值。


漫画:什么是布隆算法?



2.把第二个URL也按照三种Hash算法,分别生成三个不同的Hash值。


漫画:什么是布隆算法?



3.依次比较每一个Hash结果,只有当全部结果都相等时,才判定两个URL相同。


漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



具体怎样映射呢?流程如下:


1.创建一个空的Bitmap集合。


漫画:什么是布隆算法?



2.把第一个URL按照三种Hash算法,分别生成三个不同的Hash值。


漫画:什么是布隆算法?



3.分别判断5,17, 9 在Bitmap的对应位置是否为1,只要不同时为1,就认为该Url没有重复,于是把5,17,9的对应位置设置为1。


漫画:什么是布隆算法?



4.把第二个URL按照三种Hash算法,分别生成三个不同的Hash值。


漫画:什么是布隆算法?



5.分别判断10,12, 9 在Bitmap的对应位置是否为1,只要不同时为1,就认为该Url没有重复,于是把10,12, 9 的对应位置设置为1。


漫画:什么是布隆算法?


6.把第三个URL按照三种Hash算法,分别生成三个不同的Hash值。


漫画:什么是布隆算法?



7.分别判断4,16, 11 在Bitmap的对应位置是否为1,只要不同时为1,就认为该Url没有重复,于是把4,16, 11 的对应位置设置为1。


漫画:什么是布隆算法?



8.把第四个URL按照三种Hash算法,分别生成三个不同的Hash值。


漫画:什么是布隆算法?



9.分别判断5,17, 9 在Bitmap的对应位置是否为1。判断的结果是 5,17, 9 在Bitmap对应位置的值都是1,所以判定该Url是一个重复的Url



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



1.URL按照三个Hash算法得到三个结果。


漫画:什么是布隆算法?



2.分别判断10,12, 17 在Bitmap的对应位置是否为1。判断的结果是 10,12, 17 在Bitmap对应位置的值都是1,所以判定该Url是一个重复的Url


漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?



漫画:什么是布隆算法?




—————END—————




喜欢本文的朋友们,欢迎长按下图关注订阅号梦见,收看更多精彩内容

漫画:什么是布隆算法?


原文始发于微信公众号(程序员小灰):漫画:什么是布隆算法?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 漫画:什么是布隆算法?

我还会在以下平台发布内容

GitHub 哔哩哔哩