Bloom Filter是由Bloom在1970年提出的一種多哈希函數映射的快速查找算法。通常應用在一些需要快速判斷某個元素是否屬于集合，但是并不嚴格要求100%正確的場合。

 

一. 實例 

　　為了說明Bloom Filter存在的重要意義，舉一個實例：

　　假設要你寫一個網絡蜘蛛（web crawler）。由于網絡間的鏈接錯綜復雜，蜘蛛在網絡間爬行很可能會形成“環”。為了避免形成“環”，就需要知道蜘蛛已經訪問過那些URL。給一個URL，怎樣知道蜘蛛是否已經訪問過呢？稍微想想，就會有如下幾種方案：

　　1. 將訪問過的URL保存到數據庫。

　　2. 用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價就可以查到一個URL是否被訪問過了。

　　3. URL經過MD5或SHA-1等單向哈希后再保存到HashSet或數據庫。

　　4. Bit-Map方法。建立一個BitSet，將每個URL經過一個哈希函數映射到某一位。

　　方法1~3都是將訪問過的URL完整保存，方法4則只標記URL的一個映射位。

 

總結

以上是生活随笔為你收集整理的BloomFilter——大规模数据处理利器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。