在爬蟲中，我們經(jīng)常遇到這樣的問題。一是希望抓取過的URL不再重復抓取，節(jié)省資源；二是希望下載過的數(shù)據(jù)不再重復下載（一般情況下保證了第一條可以差不多滿足第二條）。

爬蟲去重一般是對URL去重，訪問過的頁面不在訪問去重可以避免網(wǎng)絡之間的環(huán)路，并且增加爬取效率。

今天我們介紹幾個去重策略

一、像十萬以下URL的抓取可以簡單的用set來實現(xiàn)去重，可以在O(1)的時間內(nèi)查詢到一個URL是否存在于set中。

缺點：占用內(nèi)存大，比如有1億條URL，占用的內(nèi)存是：1000000000*2byte*50字符/1024/1024/1024 = 9G(假設字符使用的是unicode編碼，每一個字符占2字節(jié)，每一個URL有50個字符)。

二、如果是百萬或者千萬量級的話，考慮到性能，我們應該使用基于hash的set實現(xiàn)去重。哈希使得我們并不需要對比超長的URL以及params，只需要對比其哈希值。

缺點：如果檢測結果為是，該元素不一定在集合中；但如果檢測結果為否，該元素一定不在集合中。這樣每個檢測請求返回有“在集合內(nèi)（可能錯誤）”和“不在集合內(nèi)（絕對不在集合內(nèi)）”兩種情況，可見 Bloom filter 是犧牲了正確率和時間以節(jié)省空間。

三、URL經(jīng)過MD5或SHA-1等哈希算法生成摘要，再存到HashSet中。MD5處理后摘要長度128位，SHA-1摘要長度160位，這樣占用內(nèi)存比直接存小很多。（scrapy使用的就是類似的方法）

四、使用bitmap方法，將訪問過的URL通過hash函數(shù)映射到某一位上，這種方法可以大大壓縮URL的存儲空間，但是缺點是，會有很多的映射沖突，即多個不同的URL映射到一個位上。

五、如果數(shù)據(jù)量上億或者幾十億時使用?Bloom Filter（中文：布隆過濾器）算法。布隆過濾器原理是這樣的，一個URL過來，通過M個特別的哈希函數(shù)對其進行運算，映射成一個M維位數(shù)組的M個維度。新的URL誕生時，進行同樣操作并逐個與set中的位數(shù)組做“與”運算，若結果改變則說明URL一定沒有被抓取過，若結果一致則說明URL有一定概率被抓取過因為有一定的低錯誤率。布隆過濾器的插入和查詢效率都是O(M)，遠低于其他一般策略。使用Bloom Filter方法對bitmap進行改進，多重哈希函數(shù)降低沖突，是對（四：bitmap方法）的改進，既能降低沖突，又能大大壓縮內(nèi)存

六、像MySQL這種關系型數(shù)據(jù)庫，我們可以設置主鍵或者唯一索引來保證數(shù)據(jù)的唯一性。查詢導致效率低，不推薦。

七、像MongoDB這種Schema free的非關系型數(shù)據(jù)庫，我們可以用先檢索再插入或者是upsert的方式保證數(shù)據(jù)的唯一性。（相對于MySQL數(shù)據(jù)庫的性能有了很大的提升）

八、緩存數(shù)據(jù)庫去重： 如Redis數(shù)據(jù)庫其高速的讀寫，使用其中的Set數(shù)據(jù)類型，并可將內(nèi)存中的數(shù)據(jù)持久化，應用廣泛，推薦。

比較好的方式為：URL經(jīng)過MD5或SHA-1等哈希算法生成摘要，再存到?Redis的HashSet中

歡迎留言糾錯補充，QQ：2223136131