程序員小灰——漫畫：什麼是布隆算法？
作者：玻璃貓；
來源：程序員小灰
兩週之前——
爬蟲的原理就不細說了，無非是通過種子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—————
