漫画：什么是布隆算法？
source link: https://www.cxyxiaowu.com/3491.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
两周之前——
爬虫的原理就不细说了，无非是通过种子URL来顺藤摸瓜，爬取出网站关联的所有的子网页，存入自己的网页库当中。
但是，这其中涉及到一个小小的问题……
URL去重方案第一版：HashSet
创建一个HashSet集合，把每一个URL字符串作为HashSet的key插入到集合当中，利用HashSet的Key唯一性来对URL做去重。
这个方案看似没毛病，但是经过几轮压测之后……
每一个URL按照20字节来算，一亿个URL就是20亿字节，也就是大约占了1.8G以上的空间。这么大的HashSet集合显然是不可取的。
于是小灰又思考了一番……
URL去重方案第二版：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—————
喜欢本文的朋友们，欢迎长按下图关注订阅号梦见，收看更多精彩内容
原文始发于微信公众号（程序员小灰）：漫画：什么是布隆算法？
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK