基本概念
如果想要判斷一個元素是不是在一個集合裡，一般想到的是将所有元素保存起來，然後通過比較确定。鍊表，樹等等數據結構都是這種思路。
但是随着集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢(O(n)，O(logn))。不過世界上還有一種叫作散列表（又叫哈希表，Hash table）的數據結構。
它可以通過一個Hash函數将一個元素映射成一個位陣列（Bit array）中的一個點。這樣一來，我們隻要看看這個點是不是1就可以知道集合中有沒有它了。這就是布隆過濾器的基本思想。
Hash面臨的問題就是沖突。假設Hash函數是良好的，如果我們的位陣列長度為m個點，那麼如果我們想将沖突率降低到例如1%，這個散列表就隻能容納m/100個元素。
顯然這就不叫空間效率了（Space-efficient）了。解決方法也簡單，就是使用多個Hash，如果它們有一個說元素不在集合中，那肯定就不在。
如果它們都說在，雖然也有一定可能性它們在說謊，不過直覺上判斷這種事情的概率是比較低的。
優點
相比于其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。
另外，Hash函數相互之間沒有關系，方便由硬件并行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何數據結構都不能。
缺點
但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。随着存入的元素數量增加，誤算率随之增加。但是如果元素數量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中删除元素。我們很容易想到把位列陣變成整數數組，每插入一個元素相應的計數器加1，這樣删除元素時将計數器減掉就可以了。
然而要保證安全的删除元素并非如此簡單。首先我們必須保證删除的元素的确在布隆過濾器裡面.這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。
在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。
應用
網頁URL的去重，垃圾郵件的判别，集合重複元素的判别，查詢加速（比如基于key-value的存儲系統）、數據庫防止查詢擊穿， 使用BloomFilter來減少不存在的行或列的磁盤查找。
java代碼實現
public class MyBloomFilter {
/**
* 一個長度為10 億的比特位
*/
private static final int DEFAULT_SIZE = 256 << 22;
/**
* 為了降低錯誤率，使用加法hash算法，所以定義一個8個元素的質數數組
*/
private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
/**
* 相當于構建 8 個不同的hash算法
*/
private static HashFunction[] functions = new HashFunction[seeds.length];
/**
* 初始化布隆過濾器的 bitmap
*/
private static BitSet bitset = new BitSet(DEFAULT_SIZE);
/**
* 添加數據
*
* @param value 需要加入的值
*/
public static void add(String value) {
if (value != null) {
for (HashFunction f : functions) {
//計算 hash 值并修改 bitmap 中相應位置為 true
bitset.set(f.hash(value), true);
}
}
}
/**
* 判斷相應元素是否存在
* @param value 需要判斷的元素
* @return 結果
*/
public static boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (HashFunction f : functions) {
ret = bitset.get(f.hash(value));
//一個 hash 函數返回 false 則跳出循環
if (!ret) {
break;
}
}
return ret;
}
/**
* 測試。。。
*/
public static void main(String[] args) {
for (int i = 0; i < seeds.length; i++) {
functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
}
// 添加1億數據
for (int i = 0; i < 100000000; i++) {
add(String.valueOf(i));
}
String id = "123456789";
add(id);
System.out.println(contains(id)); // true
System.out.println("" + contains("234567890")); //false
}
}
class HashFunction {
private int size;
private int seed;
public HashFunction(int size, int seed) {
this.size = size;
this.seed = seed;
}
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
int r = (size - 1) & result;
return (size - 1) & result;
}
}
