三種去重方式

---

去重就有三種實現(xiàn)方式，那有什么不同呢？

HashSet

使用java中的HashSet不能重復(fù)的特點去重。優(yōu)點是容易理解。使用方便。

缺點：占用內(nèi)存大，性能較低。

Redis去重

使用Redis的set進(jìn)行去重。優(yōu)點是速度快（Redis本身速度就很快），而且去重不會占用爬蟲服務(wù)器的資源，可以處理更大數(shù)據(jù)量的數(shù)據(jù)爬取。

缺點：需要準(zhǔn)備Redis服務(wù)器，增加開發(fā)和使用成本。

布隆過濾器（BloomFilter）

使用布隆過濾器也可以實現(xiàn)去重。優(yōu)點是占用的內(nèi)存要比使用HashSet要小的多，也適合大量數(shù)據(jù)的去重操作。

缺點：有誤判的可能。沒有重復(fù)可能會判定重復(fù)，但是重復(fù)數(shù)據(jù)一定會判定重復(fù)。

---

---

布隆過濾器（BloomFilter）

布隆過濾器 (Bloom Filter)是由Burton Howard Bloom于1970年提出，它是一種space efficient的概率型數(shù)據(jù)結(jié)構(gòu)，用于判斷一個元素是否在集合中。在垃圾郵件過濾的黑白名單方法、爬蟲(Crawler)的網(wǎng)址判重模塊中等等經(jīng)常被用到。

哈希表也能用于判斷元素是否在集合中，但是布隆過濾器只需要哈希表的1/8或1/4的空間復(fù)雜度就能完成同樣的問題。

布隆過濾器可以插入元素，但不可以刪除已有元素。其中的元素越多，誤報率越大，但是漏報是不可能的。

原理：

布隆過濾器需要的是一個位數(shù)組(和位圖類似)和K個映射函數(shù)(和Hash表類似)，在初始狀態(tài)時，對于長度為m的位數(shù)組array，它的所有位被置0。

?

對于有n個元素的集合S={S1,S2...Sn},通過k個映射函數(shù){f1,f2,......fk}，將集合S中的每個元素Sj(1<=j<=n)映射為K個值{g1,g2...gk}，然后再將位數(shù)組array中相對應(yīng)的array[g1],array[g2]......array[gk]置為1：

?

如果要查找某個元素item是否在S中，則通過映射函數(shù){f1,f2,...fk}得到k個值{g1,g2...gk}，然后再判斷array[g1],array[g2]...array[gk]是否都為1，若全為1，則item在S中，否則item不在S中。

布隆過濾器會造成一定的誤判，因為集合中的若干個元素通過映射之后得到的數(shù)值恰巧包括g1,g2,...gk，在這種情況下可能會造成誤判，但是概率很小。

總結(jié)

以上是生活随笔為你收集整理的三种去重方式——HashSet、Redis去重、布隆过滤器（BloomFilter）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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