漫画算法：布隆算法
image
image
image
image
两周之前——
image
image
image
爬虫的原理就不细说了，无非是通过种子URL来顺藤摸瓜，爬取出网站关联的所有的子网页，存入自己的网页库当中。
image
但是，这其中涉及到一个小小的问题......
image
image
URL去重方案第一版：HashSet
创建一个HashSet集合，把每一个URL字符串作为HashSet的key插入到集合当中，利用HashSet的Key唯一性来对URL做去重。
image
这个方案看似没毛病，但是经过几轮压测之后......
image
每一个URL按照20字节来算，一亿个URL就是20亿字节，也就是大约占了1.8G以上的空间。这么大的HashSet集合显然是不可取的。
于是小灰又思考了一番......
image
URL去重方案第二版：Bitmap
Bitmap是一种节省空间的数据结构，不太了解的朋友可以看看往期的相关文章：
具体怎么做呢？获取每一个URL的HashCode，根据HashCode的值来插入到Bitmap的对应位置。如果要插入位置的值已经是1，说明该URL已重复。
image
使用Bitmap以后，每一个Url只占了1个Bit，一亿个Url占约12MB。假设整个Bitmap的空隙比较多，额外空间占90%，总空间也不过是120MB，相比HashSet来说大大节省了内存空间。
这个方案貌似好了很多，可是......
image
String的Hashcode方法虽然尽可能做到均匀分布，但仍然免不了会有冲突的情况。HashCode的冲突意味着什么呢？意味着两个原本并不相同的Url被误判为重复Url。
image
———————————————
image
image
image
image
image
image
image
image
image
image
image
image
听起来有点绕，我们来详细描述一下：
1.把第一个URL按照三种Hash算法，分别生成三个不同的Hash值。
image
2.把第二个URL也按照三种Hash算法，分别生成三个不同的Hash值。
image
3.依次比较每一个Hash结果，只有当全部结果都相等时，才判定两个URL相同。
image
image
image
具体怎样映射呢？流程如下：
1.创建一个空的Bitmap集合。
image
2.把第一个URL按照三种Hash算法，分别生成三个不同的Hash值。
image
3.分别判断5，17， 9 在Bitmap的对应位置是否为1，只要不同时为1，就认为该Url没有重复，于是把5，17，9的对应位置设置为1。
image
4.把第二个URL按照三种Hash算法，分别生成三个不同的Hash值。
image
5.分别判断10，12， 9 在Bitmap的对应位置是否为1，只要不同时为1，就认为该Url没有重复，于是把10，12， 9 的对应位置设置为1。
image
6.把第三个URL按照三种Hash算法，分别生成三个不同的Hash值。
image
7.分别判断4，16， 11 在Bitmap的对应位置是否为1，只要不同时为1，就认为该Url没有重复，于是把4，16， 11 的对应位置设置为1。
image
8.把第四个URL按照三种Hash算法，分别生成三个不同的Hash值。
image
9.分别判断5，17， 9 在Bitmap的对应位置是否为1。判断的结果是 5，17， 9 在Bitmap对应位置的值都是1，所以判定该Url是一个重复的Url。
image
image
image
1.URL按照三个Hash算法得到三个结果。
image
2.分别判断10，12， 17 在Bitmap的对应位置是否为1。判断的结果是 10，12， 17 在Bitmap对应位置的值都是1，所以判定该Url是一个重复的Url。
image
image
image
image
image
image
image
image
From: http://posts.careerengine.us/p/59c1039fc7987e3c8b8214ea
