轉(zhuǎn)載自?玻璃貓 程序員小灰

兩周之前——

爬蟲的原理就不細(xì)說了，無非是通過種子URL來順藤摸瓜，爬取出網(wǎng)站關(guān)聯(lián)的所有的子網(wǎng)頁，存入自己的網(wǎng)頁庫當(dāng)中。

但是，這其中涉及到一個小小的問題......

URL去重方案第一版：HashSet

創(chuàng)建一個HashSet集合，把每一個URL字符串作為HashSet的key插入到集合當(dāng)中，利用HashSet的Key唯一性來對URL做去重。

這個方案看似沒毛病，但是經(jīng)過幾輪壓測之后......

每一個URL按照20字節(jié)來算，一億個URL就是20億字節(jié)，也就是大約占了1.8G以上的空間。這么大的HashSet集合顯然是不可取的。

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

URL去重方案第二版：Bitmap

具體怎么做呢？獲取每一個URL的HashCode，根據(jù)HashCode的值來插入到Bitmap的對應(yīng)位置。如果要插入位置的值已經(jīng)是1，說明該URL已重復(fù)。

使用Bitmap以后，每一個Url只占了1個Bit，一億個Url占約12MB。假設(shè)整個Bitmap的空隙比較多，額外空間占90%，總空間也不過是120MB，相比HashSet來說大大節(jié)省了內(nèi)存空間。

這個方案貌似好了很多，可是......

String的Hashcode方法雖然盡可能做到均勻分布，但仍然免不了會有沖突的情況。HashCode的沖突意味著什么呢？意味著兩個原本并不相同的Url被誤判為重復(fù)Url。

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

聽起來有點繞，我們來詳細(xì)描述一下：

1.把第一個URL按照三種Hash算法，分別生成三個不同的Hash值。

2.把第二個URL也按照三種Hash算法，分別生成三個不同的Hash值。

3.依次比較每一個Hash結(jié)果，只有當(dāng)全部結(jié)果都相等時，才判定兩個URL相同。

具體怎樣映射呢？流程如下：

1.創(chuàng)建一個空的Bitmap集合。

2.把第一個URL按照三種Hash算法，分別生成三個不同的Hash值。

3.分別判斷5，17， 9 在Bitmap的對應(yīng)位置是否為1，只要不同時為1，就認(rèn)為該Url沒有重復(fù)，于是把5，17，9的對應(yīng)位置設(shè)置為1。

4.把第二個URL按照三種Hash算法，分別生成三個不同的Hash值。

5.分別判斷10，12， 9 在Bitmap的對應(yīng)位置是否為1，只要不同時為1，就認(rèn)為該Url沒有重復(fù)，于是把10，12， 9 的對應(yīng)位置設(shè)置為1。

6.把第三個URL按照三種Hash算法，分別生成三個不同的Hash值。

7.分別判斷4，16， 11 在Bitmap的對應(yīng)位置是否為1，只要不同時為1，就認(rèn)為該Url沒有重復(fù)，于是把4，16， 11 的對應(yīng)位置設(shè)置為1。

8.把第四個URL按照三種Hash算法，分別生成三個不同的Hash值。

9.分別判斷5，17， 9?在Bitmap的對應(yīng)位置是否為1。判斷的結(jié)果是?5，17， 9?在Bitmap對應(yīng)位置的值都是1，所以判定該Url是一個重復(fù)的Url。

1.URL按照三個Hash算法得到三個結(jié)果。

2.分別判斷10，12， 17?在Bitmap的對應(yīng)位置是否為1。判斷的結(jié)果是?10，12， 17?在Bitmap對應(yīng)位置的值都是1，所以判定該Url是一個重復(fù)的Url。

—————END—————

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的漫画：什么是布隆算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。