爬蟲數據去重： 使用MD5生成指紋判斷頁面是否變化 數據存入mongodb，對關鍵字進行複合索引（千萬以下） 對數據關鍵字進行哈希映射，生成指紋判斷是否在redis的指紋集合中，並可通過是否過濾判斷request對象是否進隊，對request對象進行過濾（千萬級別） 布隆過濾器，實現大數據去重（億級 ...
爬蟲數據去重：
- 使用MD5生成指紋判斷頁面是否變化
- 數據存入mongodb，對關鍵字進行複合索引（千萬以下）
- 對數據關鍵字進行哈希映射，生成指紋判斷是否在redis的指紋集合中，並可通過是否過濾判斷request對象是否進隊，對request對象進行過濾（千萬級別）
- 布隆過濾器，實現大數據去重（億級別）
布隆過濾器：
實現：
- 先通過預期失誤率p、期望樣本數量n，計算需要的位數組長度m
m=-n*lnp / (ln2)**2
- 再計算哈希函數個數k
k=ln2 * m/n
- 再根據m、n、k，計算真實的失誤率，因為m，k向上調整，所以真實失誤率 < 預期失誤率
p=(1-e**(-nk/m))**k
- 將數據(key)通過k個哈希函數得到k個哈希值
- 將得到的哈希值對m取模運算，得到位數組對應的索引位置
index=HashCode(key)&(m-1)
- 如果保存，將位數組中對應的索引位置變為1
- 如果查詢，判斷位數組對應的索引是否全為1，全為1則存在
原理：hashmap
- 可以將值映射到hashmap的key，在O(1)時間複雜度內返回結果
- hashmap的預設長度為16，每次擴展都是2的次冪
哈希函數特性：
- 哈希碰撞：哈希函數不同的輸入可以得到相同輸出結果，輸入域有限，輸出域無限
- 離散性：輸出域每個結果在整個輸出域中都是均勻分佈的
