看見了海量資料去重，找到停留時間最長的IP等問題，有博友提到了Bloom Filter，我就查了查，不過首先想到的是大叔，下面就先看看大叔的風采。
一、布隆過濾器概念引入
（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它實際上是由一個很長的二進制向量和一系列随機映射函數組成，布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識别率（假正例False positives，即Bloom Filter報告某一進制素存在于某集合中，但是實際上該元素并不在集合中）和删除困難，但是沒有識别錯誤的情形（即假反例False negatives，如果某個元素确實在該集合中，那麼Bloom Filter 是不會報告該元素不存在于集合中的，是以不會漏報）。
下面從簡單的排序談到BitMap算法，再談到資料去重問題，談到大資料量處理利器：布隆過濾器。
- 對無重複的資料進行排序
給定資料（2，4，1，12，9，7，6）如何對它排序？
方法1：基本的排序方法包括冒泡，快排等。
方法2：使用BitMap算法
方法1就不介紹了，方法2中所謂的BitMap是一個位數組，跟平時使用的數組的唯一差别在于操作的是位。首先是開辟2個位元組大小的位數組，長度為12（該長度由上述資料中最大的數字12決定的),然後，讀取資料，2存放在位數組中下标為1的地方，值從0改為1，4存放在下标為3的地方，值從0改為1....最後，讀取該位數組，得到排好序的資料是：（1，2，4，6，7，9，12）。
比較方法1和方法2的差别：方法2中，排序需要的時間複雜度和空間複雜度很依賴與資料中最大的數字比如12，是以空間上講需要開2個位元組大小的記憶體，時間上需要周遊完整個數組。當資料類似（1，1000，10萬）隻有3個資料的時候，顯然用方法2，時間複雜度和空間複雜度相當大，但是當資料比較密集時該方法就會顯示出來優勢。
- 對有重複的資料進行判重
資料（2，4，1，12，2，9，7，6，1，4）如何找出重複出現的數字？
首先是開辟2個位元組大小的位數組，長度為12（該長度由上述資料中最大的數字12決定的,當讀取完12後，當讀取2的時候，發現數組中的值是1，則判斷出2是重複出現的。
二、布隆過濾器原理
布隆過濾器需要的是一個位數組（這個和位圖有點類似）和k個映射函數（和Hash表類似），在初始狀态時，對于長度為m的位數組array，它的所有位都被置為0。對于有n個元素的集合S={s1,s2......sn}，通過k個映射函數{f1,f2,......fk}，将集合S中的每個元素sj(1<=j<=n)映射為k個值{g1,g2......gk}，然後再将位數組array中相對應的array[g1],array[g2]......array[gk]置為1；如果要查找某個元素item是否在S中，則通過映射函數{f1,f2.....fk}得到k個值{g1,g2.....gk}，然後再判斷array[g1],array[g2]......array[gk]是否都為1，若全為1，則item在S中，否則item不在S中。這個就是布隆過濾器的實作原理。
當然有讀者可能會問：即使array[g1],array[g2]......array[gk]都為1，能代表item一定在集合S中嗎？不一定，因為有這個可能：就是集合中的若幹個元素通過映射之後得到的數值恰巧包括g1,g2,.....gk，那麼這種情況下可能會造成誤判，但是這個機率很小，一般在萬分之一以下。
很顯然，布隆過濾器的誤判率和這k個映射函數的設計有關，到目前為止，有很多人設計出了很多高效實用的hash函數。尤其要注意的是，布隆過濾器是不允許删除元素的(實際就是因為多個str可能都應設在同一點，而判斷str存在的話是所有映射點都存在，是以不能删除)，因為若删除一個元素，可能會發生漏判的情況。不過有一種布隆過濾器的變體Counter Bloom Filter，可以支援删除元素，感興趣的讀者可以查閱相關文獻資料。
三、布隆過濾器False positives 機率推導
假設 Hash 函數以等機率條件選擇并設定 Bit Array 中的某一位，m 是該位數組的大小，k 是 Hash 函數的個數，那麼位數組中某一特定的位在進行元素插入時的 Hash 操作中沒有被置位為1的機率是：
；那麼在所有 k 次 Hash 操作後該位都沒有被置 "1" 的機率是：
；如果我們插入了 n 個元素，那麼某一位仍然為 "0" 的機率是：
因而該位為 "1"的機率是：
；現在檢測某一進制素是否在該集合中。标明某個元素是否在集合中所需的 k 個位置都按照如上的方法設定為 "1"，但是該方法可能會使算法錯誤的認為某一原本不在集合中的元素卻被檢測為在該集合中（False Positives），該機率由以下公式确定：
。
其實上述結果是在假定由每個 Hash 計算出需要設定的位（bit） 的位置是互相獨立為前提計算出來的，不難看出，随着 m （位數組大小）的增加，假正例（False Positives）的機率會下降，同時随着插入元素個數 n 的增加，False Positives的機率又會上升，對于給定的m，n，如何選擇Hash函數個數 k 由以下公式确定：
；此時False Positives的機率為：
；而對于給定的False Positives機率 p，如何選擇最優的位數組大小 m 呢，
；該式表明，位數組的大小最好與插入元素的個數成線性關系，對于給定的 m，n，k，假正例機率最大為：
四、布隆過濾器應用
布隆過濾器在很多場合能發揮很好的效果，比如：網頁URL的去重，垃圾郵件的判别，集合重複元素的判别，查詢加速（比如基于key-value的存儲系統）等，下面舉幾個例子：
- 有兩個URL集合A,B，每個集合中大約有1億個URL，每個URL占64位元組，有1G的記憶體，如何找出兩個集合中重複的URL。
很顯然，直接利用Hash表會超出記憶體限制的範圍。這裡給出兩種思路：
第一種：如果不允許一定的錯誤率的話，隻有用分治的思想去解決，将A,B兩個集合中的URL分别存到若幹個檔案中{f1,f2...fk}和{g1,g2....gk}中，然後取f1和g1的内容讀入記憶體，将f1的内容存儲到hash_map當中，然後再取g1中的url，若有相同的url，則寫入到檔案中，然後直到g1的内容讀取完畢，再取g2...gk。然後再取f2的内容讀入記憶體。。。依次類推，知道找出所有的重複url。
第二種：如果允許一定錯誤率的話，則可以用布隆過濾器的思想。
- 在進行網頁爬蟲時，其中有一個很重要的過程是重複URL的判别，如果将所有的url存入到資料庫中，當資料庫中URL的數
量很多時，在判重時會造成效率低下，此時常見的一種做法就是利用布隆過濾器，還有一種方法是利用berkeley db來存儲url，Berkeley db是一種基于key-value存儲的非關系資料庫引擎，能夠大大提高url判重的效率。
布隆過濾器主要運用在過濾惡意網址用的，将所有的惡意網址建立在一個布隆過濾器上，然後對使用者的通路的網址進行檢測，如果在惡意網址中那麼就通知使用者。這樣的話，我們還可以對一些常出現判斷錯誤的網址設定一個白名單，然後對出現判斷存在的網址再和白名單中的網址進行比對，如果在白名單中，那麼就放行。當然這個白名單不能太大，也不會太大，布隆過濾器錯誤的機率是很小的。
五、布隆過濾器簡單Java實作
package a;
import java.util.BitSet;
/*
* 存在的問題
* DEFAULT_LEN長度設定為多少合适呢？
* 我發現result和DEFAULT_LEN有關，不應該啊，沒發現原因
*/
public class BloomFilterTest {
//30位，表示2^2^30種字元
static int DEFAULT_LEN = 1<<30;
//要用質數
static int[] seeds = {3,5,7,11,17,31};
static BitSet bitset = new BitSet(DEFAULT_LEN);
static MyHash[] myselfHash = new MyHash[seeds.length];
public static void main(String[] args) {
String str = "[email protected]";
//生成一次就夠了
for(int i=0; i<seeds.length; i++) {
myselfHash[i] = new MyHash(DEFAULT_LEN, seeds[i]);
}
bitset.clear();
for(int i=0; i<myselfHash.length; i++) {
bitset.set(myselfHash[i].myHash(str),true);
}
boolean flag = containsStr(str);
//System.out.println("========================");
System.out.println(flag);
}
private static boolean containsStr(String str) {
// TODO Auto-generated method stub
if(null==str)
return false;
for(int i=0; i<seeds.length; i++) {
if(bitset.get(myselfHash[i].myHash(str))==false)
return false;
}
return true;
}
}
class MyHash {
int len;
int seed;
public MyHash(int len, int seed) {
super();
this.len = len;
this.seed = seed;
}
public int myHash(String str) {
int len = str.length();
int result = 0;
//這的len就是str的len，不是成員變量的len
for(int i=0; i<len; i++) {
//System.out.println(seed+"oooooooooooo");
result = result*seed + str.charAt(i);
//System.out.println(result);
//長度就是1<<24，如果大于這個數 感覺結果不準确
//<0就是大于了0x7ffffff
if(result>(1<<30) || result<0) {
//System.out.println("-----"+(1<<30));
System.out.println(result+"myHash資料越界！！！");
break;
}
}
return (len-1)&result;
}
}