布隆過濾器在HBase中的應用 - Echo的博客 - 博客頻道 - CSDN.NET
http://blog.csdn.net/echozhan/article/details/53154009

在討論布隆過濾器在Hbase中的應用之前，先介紹一下HBase的塊索引機制。塊索引是HBase固有的一個特性，因為HBase的底層數(shù)據(jù)是存儲在HFile中的，而每個HFile中存儲的是有序的<key, value>鍵值對，HFile文件內(nèi)部由連續(xù)的塊組成[1]，每個塊中存儲的第一行數(shù)據(jù)的行鍵組成了這個文件的塊索引，這些塊索引信息存儲在文件尾部。當HBase打開一個HFile時，塊索引信息會優(yōu)先加載到內(nèi)存；HBase首先在內(nèi)存的塊索引中進行二分查找，確定可能包含給定鍵的塊，然后讀取磁盤塊找到實際想要的鍵。

但實際應用中，僅僅只有塊索引滿足不了需求，這是因為，塊索引能幫助我們更快地在一個文件中找到想要的數(shù)據(jù)，但是我們可能依然需要掃描很多文件。而布隆過濾器就是為解決這個問題而生。因為布隆過濾器的作用是，用戶可以立即判斷一個文件是否包含特定的行鍵，從而幫我們過濾掉一些不需要掃描的文件。如下圖所示，塊索引顯示每個文件中都可能包含對應的行鍵，而布隆過濾器能幫我們跳過一些明顯不包含對應行鍵的文件。

HBase–常用過濾器篇 - 圈里圈外 - 開源中國社區(qū)
https://my.oschina.net/circleblog/blog/715724

5. 布隆過濾器 BloomFilter簡介：hbase的storefile有很多，隨機查的時候可能需要遍歷很多storefile，如果在建表的時候指定了bloomfilter，則在get查詢（scan不管用）的時候就可以過濾掉很多不符合規(guī)則的storefile，提高查詢效率。

從另一個角度看大數(shù)據(jù)量處理利器：布隆過濾器 - 寒山拾得 - 博客頻道 - CSDN.NET
http://blog.csdn.net/u013467442/article/details/41150241

思路：從簡單的排序談到BitMap算法，再談到數(shù)據(jù)去重問題，談到大數(shù)據(jù)量處理利器：布隆過濾器。情景1：對無重復的數(shù)據(jù)進行排序
@給定數(shù)據(jù)（2，4，1，12，9，7，6）如何對它排序？
方法1：基本的排序方法包括冒泡，快排等。
方法2：使用BitMap算法
方法1就不介紹了，方法2中所謂的BitMap是一個位數(shù)組，跟平時使用的數(shù)組的唯一差別在于操作的是位。
首先是開辟2個字節(jié)大小的位數(shù)組，長度為16（該長度由上述數(shù)據(jù)中最大的數(shù)字12決定的）如圖

  比較方法1和方法2的差別：方法2中，排序需要的時間復雜度和空間復雜度很依賴與數(shù)據(jù)中最大的數(shù)字比如12，因此空間上講需要開2個字節(jié)大小的內(nèi)存，時間上需要遍歷完整個數(shù)組。當數(shù)據(jù)類似（1，1000，10萬）只有3個數(shù)據(jù)的時候，顯然用方法2，時間復雜度和空間復雜度相當大，但是當數(shù)據(jù)比較密集時該方法就會顯示出來優(yōu)勢。

情景2：對有重復的數(shù)據(jù)進行判重
數(shù)據(jù)（2，4，1，12，2，9，7，6，1，4）如何找出重復出現(xiàn)的數(shù)字？
首先是開辟2個字節(jié)大小的位數(shù)組，長度為16（該長度由上述數(shù)據(jù)中最大的數(shù)字12決定的）如圖

  應用2：某文件中包含一些8位的電話號碼，統(tǒng)計只出現(xiàn)一次的號碼？（判斷有誰出現(xiàn)并且指出現(xiàn)1次）
  需要擴展一下，可以用兩個bit表示一個號碼，0代表沒有出現(xiàn)過，1代表只出現(xiàn)過1次，2代表至少出現(xiàn)2次。 

  應用3：有兩個文件，文件1中有1億個10位的qq號碼，文件2中有5千萬個10位qq號碼，判斷兩個文件中重復出現(xiàn)的qq號。
 首先建立10的10次方個大小的位數(shù)組（占用內(nèi)存大約是1.25G），全部初始化為0，讀取第一個文件，對應的qq號存放到對應的未知，數(shù)值改為1，如果重復出現(xiàn)仍是1.讀取完畢第一個文件后，讀取第二個文件，對應的位置為1則表示重復出現(xiàn)。

 應用4：有兩個文件，文件1中有1億個15位的qq號碼，文件2中有5千萬個15位的qq號碼，判斷兩個文件中重復出現(xiàn)的qq號。 

應用4中，qq號碼上升為15位的時候，顯然內(nèi)存是不夠用了，這個時候怎么辦？使用Bloom Filter（布隆過濾器）

Bloom Filter（布隆過濾器）：
對于Bit-Map分析一下，每次都會開辟一塊表示最大數(shù)值大小的bit數(shù)組，比如情景1中的16，將對應的數(shù)據(jù)經(jīng)過映射到bit數(shù)組的下標，這其實是一種最簡單的hash算法，對1去模。在上述應用4中，當qq號碼改為15位的時候，Bit-Map就不太好用了，如何改進呢？解決辦法：減少bit數(shù)組的長度，但是增加hash函數(shù)的個數(shù)
對于每一個qq號碼，我用K個hash函數(shù)，經(jīng)過k次映射，得到k個不同位置，假設k=3，那么對于一個qq號碼，映射到位數(shù)組中3個不同的位置

當讀取第二個包含5千萬個qq號碼的文件的時候，使用同樣的3個hash函數(shù)進行映射，當3個位置全部是1的時候才表示出現(xiàn)過，否則表示沒有出現(xiàn)過。
有什么疑問嗎？
顯然，對于一個qq號碼，如果它在第一個文件中沒有出現(xiàn)過，但是它映射的3個位置已經(jīng)全部是1的情況會有嗎？答案是會的，但是這種概率是可控的，可控的意思是：這種誤差跟hash函數(shù)的個數(shù)和質(zhì)量是有關系的，可以通過控制hash函數(shù)的個數(shù)和位數(shù)組的大小來控制誤差概率。至于表示3者之間的關系精確的數(shù)學公式就不再詳細研究了。
可以這樣講，布隆過濾器是Bit-Map的進一步擴展，對于大數(shù)據(jù)量判重，布隆過濾器可以在內(nèi)存中進行判斷，避免了對磁盤的讀寫，效率是很高的。以上是自己關于兩者的理解，有錯誤望指教。

布隆過濾（Bloom Filter）-必須了解的優(yōu)化器算法 - wwicked - 博客園
http://www.cnblogs.com/wwicked/articles/4750071.html

吳軍博士，在《數(shù)學之美》一書中，曾經(jīng)介紹過這個算法，以下內(nèi)容轉(zhuǎn)引自吳軍博士的文章：
假定我們存儲一億個電子郵件地址，我們先建立一個十六億二進制(比特)，即兩億字節(jié)的向量，然后將這十六億個二進制全部設置為零。對于每一個電子郵件地址 X，我們用八個不同的隨機數(shù)產(chǎn)生器(F1,F2, ...,F8) 產(chǎn)生八個信息指紋(f1, f2, ..., f8)。再用一個隨機數(shù)產(chǎn)生器 G 把這八個信息指紋映射到 1 到十六億中的八個自然數(shù) g1, g2, ...,g8?，F(xiàn)在我們把這八個位置的二進制全部設置為一。當我們對這一億個 email 地址都進行這樣的處理后。一個針對這些 email 地址的布隆過濾器就建成了。(見下圖)

算法分析：使用布隆過濾器（Bloom Filter）進行大數(shù)據(jù)量排序 - 苗哥的個人頁面 - 開源中國社區(qū)
https://my.oschina.net/bairrfhoinn/blog/209965

摘要: 移動公司需要對已經(jīng)發(fā)放的所有139段的號碼進行統(tǒng)計排序，已經(jīng)發(fā)放的139號碼段的文件都存放在一個文本文件中（原題是放在兩個文件中），一個號碼一行，現(xiàn)在需要將文件里的所有號碼進行排序，并寫入到一個新的文件中；號碼可能會有很多，最多可能有一億個不同的號碼（所有的139段號碼），存入文本文件中大概要占1.2G的空間；JVM最大的內(nèi)存在300以內(nèi)，程序要考慮程序的可執(zhí)行性及效率；只能使用Java標準庫，不得使用第三方工具。

  題目大意：移動公司需要對已經(jīng)發(fā)放的所有139段的號碼進行統(tǒng)計排序，已經(jīng)發(fā)放的139號碼段的文件都存放在一個文本文件中（原題是放在兩個文件中），一個號碼一行，現(xiàn)在需要將文件里的所有號碼進行排序，并寫入到一個新的文件中；號碼可能會有很多，最多可能有一億個不同的號碼（所有的139段號碼），存入文本文件中大概要占1.2G的空間；JVM最大的內(nèi)存在300以內(nèi)，程序要考慮程序的可執(zhí)行性及效率；只能使用Java標準庫，不得使用第三方工具。       這是個典型的大數(shù)據(jù)量的排序算法問題，首先要考慮空間問題，一下把.2G的數(shù)據(jù)讀入內(nèi)存是不太可能的，就算把壹億條數(shù)據(jù)都轉(zhuǎn)換成INT類型存儲也要占接近400M的空間。當時做個題目我并沒有想太多的執(zhí)行效率問題，主要就考慮了空間，而且習慣性的想到合并排序，基本思想是原文件分割成若干個小文件并排序，再將排序好的小文件合并得到最后結(jié)果，算法大概如下：1、順序讀取存放號碼文件的中所有號碼，并取139之后的八位轉(zhuǎn)換為int類型；每讀取號碼數(shù)滿一百萬個（這個數(shù)據(jù)可配置）將已經(jīng)讀取的號碼排序并存入新建的臨時文件。2、將所有生成的號碼有序的臨時文件合并存入結(jié)果文件。

這個算法雖然解決了空間問題，但是運行效率極低，由于IO讀寫操作太多，加上步驟1中的排序的算法（快速排序）本來效率就不高（對于電話排序這種特殊情況來說），導致1億條數(shù)據(jù)排序運行3個小時才有結(jié)果。 如何能夠減少排序的時間呢？首當其沖的是減少IO操作，另外如果能夠有更加好排序算法也行。前天無聊再看這個題目時突然想到大三時看《編程珠璣》時上面也有個問題的需求這個這個題目差不多，記得好像使用是位向量（實際上就是一個bit數(shù)組），用電話作為index，心中大喜，找到了解決此問題的最完美方案：用位向量存儲電話號碼，壹個號碼占壹個bit，壹億個電話號碼也只需要大概12M的空間；算法大概如下：1、初始化bits[capacity]；2、順序所有讀入電話號碼，并轉(zhuǎn)換為int類型，修改位向量值：bits[phoneNum]=1；3、遍歷bits數(shù)組，如果bits[index]=1，轉(zhuǎn)換index為電話號碼輸出。

由于Java中沒有 bit 類型，一個 boolean 值占空間為 1byte（感興趣的可以自己寫程序驗證），我自己寫了個用 int 模擬 bit 數(shù)組的類，代碼如下：

互聯(lián)網(wǎng)大數(shù)據(jù)采集與處理的關鍵技術研究金融大數(shù)據(jù)科技
http://www.cfc365.com/technology/bigdata/2015-03-04/13202.shtml

3．數(shù)據(jù)采集的關鍵技術——鏈接過濾
鏈接過濾的實質(zhì)就是判斷一個鏈接（當前鏈接）是不是在一個鏈接集合（已經(jīng)抓取過的鏈接）里面。在對網(wǎng)頁大數(shù)據(jù)的采集中，可以采用布隆過濾器來實現(xiàn)對鏈接的過濾。

布隆過濾器（Bloom Filter）的基本思想是：當一個元素被加入集合時，通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是l，則被檢元素很可能在。
布隆過濾器在空間和時間方面都有巨大的優(yōu)勢：
（1）在復雜度方面，布隆過濾器存儲空間和插入／查詢時間都是常數(shù)（即復雜度為O(k)）； （2）在關系方面，散列函數(shù)相互之間沒有關聯(lián)關系，方便由硬件并行實現(xiàn)； （3）在存儲方面，布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優(yōu)勢。
布隆過濾器的具體實現(xiàn)方法是，已經(jīng)抓取過的每個URL，經(jīng)過k個hash函數(shù)的計算，得出k個值，再和一個巨大bit數(shù)組的這k個位置的元素對應起來（這些位置數(shù)組元素的值被設置為1）。在需要判斷某個URL是否被抓取過時，先用k個hash函數(shù)對該URL計算出k個值，然后查詢巨大的bit數(shù)組內(nèi)這k個位置上的值，如果全為l，則是已經(jīng)被抓取過，否則沒有被抓取過。

海量數(shù)據(jù)處理利器之布隆過濾器 - 火星十一郎 - 博客園
http://www.cnblogs.com/hxsyl/p/4176280.html

四、布隆過濾器應用
布隆過濾器在很多場合能發(fā)揮很好的效果，比如：網(wǎng)頁URL的去重，垃圾郵件的判別，集合重復元素的判別，查詢加速（比如基于key-value的存儲系統(tǒng)）等，下面舉幾個例子：
有兩個URL集合A,B，每個集合中大約有1億個URL，每個URL占64字節(jié)，有1G的內(nèi)存，如何找出兩個集合中重復的URL。

很顯然，直接利用Hash表會超出內(nèi)存限制的范圍。這里給出兩種思路：
第一種：如果不允許一定的錯誤率的話，只有用分治的思想去解決，將A,B兩個集合中的URL分別存到若干個文件中{f1,f2...fk}和{g1,g2....gk}中，然后取f1和g1的內(nèi)容讀入內(nèi)存，將f1的內(nèi)容存儲到hash_map當中，然后再取g1中的url，若有相同的url，則寫入到文件中，然后直到g1的內(nèi)容讀取完畢，再取g2...gk。然后再取f2的內(nèi)容讀入內(nèi)存。。。依次類推，知道找出所有的重復url。
第二種：如果允許一定錯誤率的話，則可以用布隆過濾器的思想。
在進行網(wǎng)頁爬蟲時，其中有一個很重要的過程是重復URL的判別，如果將所有的url存入到數(shù)據(jù)庫中，當數(shù)據(jù)庫中URL的數(shù)

量很多時，在判重時會造成效率低下，此時常見的一種做法就是利用布隆過濾器，還有一種方法是利用berkeley db來存儲url，Berkeley db是一種基于key-value存儲的非關系數(shù)據(jù)庫引擎，能夠大大提高url判重的效率。
布隆過濾器主要運用在過濾惡意網(wǎng)址用的，將所有的惡意網(wǎng)址建立在一個布隆過濾器上，然后對用戶的訪問的網(wǎng)址進行檢測，如果在惡意網(wǎng)址中那么就通知用戶。這樣的話，我們還可以對一些常出現(xiàn)判斷錯誤的網(wǎng)址設定一個白名單，然后對出現(xiàn)判斷存在的網(wǎng)址再和白名單中的網(wǎng)址進行匹配，如果在白名單中，那么就放行。當然這個白名單不能太大，也不會太大，布隆過濾器錯誤的概率是很小的。