布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。

中文名

布隆過濾器

外文名

Bloom Filter

提出者

布隆

提出時間

1970年

基本概念

如果想要判斷一個元素是不是在一個集合里，一般想到的是將所有元素保存起來，然后通過比較確定。鏈表，樹等等數(shù)據(jù)結(jié)構(gòu)都是這種思路. 但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢

。不過世界上還有一種叫作散列表（又叫哈希表，Hash table）的數(shù)據(jù)結(jié)構(gòu)。它可以通過一個Hash函數(shù)將一個元素映射成一個位陣列（Bit array）中的一個點。這樣一來，我們只要看看這個點是不是1就可以知道集合中有沒有它了。這就是布隆過濾器的基本思想。

Hash面臨的問題就是沖突。假設(shè)Hash函數(shù)是良好的，如果我們的位陣列長度為m個點，那么如果我們想將沖突率降低到例如 1%, 這個散列表就只能容納

個元素。顯然這就不叫空間效率了（Space-efficient）了。解決方法也簡單，就是使用多個Hash，如果它們有一個說元素不在集合中，那肯定就不在。如果它們都說在，雖然也有一定可能性它們在說謊，不過直覺上判斷這種事情的概率是比較低的。

布隆過濾器

優(yōu)點

相比于其它的數(shù)據(jù)結(jié)構(gòu)，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。布隆過濾器存儲空間和插入/查詢時間都是常數(shù)。另外, Hash函數(shù)相互之間沒有關(guān)系，方便由硬件并行實現(xiàn)。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢。

布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能。

缺點

但是布隆過濾器的缺點和優(yōu)點一樣明顯。誤算率是其中之一。隨著存入的元素數(shù)量增加，誤算率隨之增加。常見的補救辦法是建立一個小的白名單，存儲那些可能被誤判的元素。但是如果元素數(shù)量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數(shù)數(shù)組，每插入一個元素相應(yīng)的計數(shù)器加1, 這樣刪除元素時將計數(shù)器減掉就可以了。然而要保證安全的刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點單憑這個過濾器是無法保證的。另外計數(shù)器回繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現(xiàn)了很多布隆過濾器的變種。

應(yīng)用

網(wǎng)頁URL的去重，垃圾郵件的判別，集合重復(fù)元素的判別，查詢加速（比如基于key-value的存儲系統(tǒng)）、數(shù)據(jù)庫防止查詢擊穿，使用BloomFilter來減少不存在的行或列的磁盤查找。

java代碼實現(xiàn)

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697public class MyBloomFilter {?????/**?????* 一個長度為10 億的比特位?????*/????private static final int DEFAULT_SIZE = 256 << 22;?????/**?????* 為了降低錯誤率，使用加法hash算法，所以定義一個8個元素的質(zhì)數(shù)數(shù)組?????*/????private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};?????/**?????* 相當(dāng)于構(gòu)建 8 個不同的hash算法?????*/????private static HashFunction[] functions = new HashFunction[seeds.length];?????/**?????* 初始化布隆過濾器的 bitmap?????*/????private static BitSet bitset = new BitSet(DEFAULT_SIZE);?????/**?????* 添加數(shù)據(jù)?????*?????* @param value 需要加入的值?????*/????public static void add(String value) {????????if (value != null) {????????????for (HashFunction f : functions) {????????????????//計算 hash 值并修改 bitmap 中相應(yīng)位置為 true????????????????bitset.set(f.hash(value), true);????????????}????????}????}?????/**?????* 判斷相應(yīng)元素是否存在?????* @param value 需要判斷的元素?????* @return 結(jié)果?????*/????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 函數(shù)返回 false 則跳出循環(huán)????????????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億數(shù)據(jù)????????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;????}}