概述

布隆過濾器(Bloom Filter)是1970年由布隆提出的。它實際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)，布隆過濾器可以用于檢索一個元素是否在一個集合中。

如果想要判斷一個元素是不是在一個集合里，一般想到的是將所有元素保存起來，然后通過比較確定。鏈表，樹等等數(shù)據(jù)結(jié)構(gòu)都是這種思路. 但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢(O(n),O(logn))。不過還有一種叫作散列表(又叫哈希表，Hash table)的數(shù)據(jù)結(jié)構(gòu)，它可以通過一個Hash函數(shù)將一個元素映射成一個位陣列中的一個點，這樣一來，我們只要看看這個點是不是1就可以知道集合中有沒有它了。這就是布隆過濾器的基本思想。

算法

1、首先需要k個hash函數(shù)，每個函數(shù)可以把key散列成為1個整數(shù)；

2、初始化時，需要一個長度為n比特的數(shù)組，每個比特位初始化為0；

3、某個key加入集合時，用k個hash函數(shù)計算出k個散列值，并把數(shù)組中對應(yīng)的比特位置為1；

4、判斷某個key是否在集合時，用k個hash函數(shù)計算出k個散列值，并查詢數(shù)組中對應(yīng)的比特位，如果所有的比特位都是1，認(rèn)為在集合中；

原理

布隆過濾器需要的是一個位數(shù)組（這個和位圖有點類似）和k個映射函數(shù)（和Hash表類似），在初始狀態(tài)時，對于長度為m的位數(shù)組array，它的所有位都被置為0，如下圖所示：

對于有n個元素的集合S={s₁,s₂......s_n}，通過k個映射函數(shù){f₁,f₂,......f_k}，將集合S中的每個元素s_j(1<=j<=n)映射為k個值{g₁,g₂......g_k}，然后再將位數(shù)組array中相對應(yīng)的array[g₁],array[g₂]......array[g_k]置為1：

如果要查找某個元素item是否在S中，則通過映射函數(shù){f1,f2.....fk}得到k個值{g1,g2.....gk}，然后再判斷array[g1],array[g2]......array[gk]是否都為1，若全為1，則item在S中，否則item不在S中。這個就是布隆過濾器的實現(xiàn)原理。

布隆過濾器優(yōu)點

它的優(yōu)點是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，布隆過濾器存儲空間和插入 / 查詢時間都是常數(shù)O(k)。另外, 散列函數(shù)相互之間沒有關(guān)系，方便由硬件并行實現(xiàn)。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢。

布隆過濾器缺點

但是布隆過濾器的缺點和優(yōu)點一樣明顯。誤算率是其中之一。隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。

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

如何選擇哈希函數(shù)個數(shù)和布隆過濾器長度

過小的布隆過濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩祷?ldquo;可能存在”，起不到過濾的目的了。布隆過濾器的長度會直接影響誤報率，布隆過濾器越長其誤報率越小。

哈希函數(shù)的個數(shù)也需要權(quán)衡，個數(shù)越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，那我們的誤報率會變高

k 為哈希函數(shù)個數(shù)，m 為布隆過濾器長度，n 為插入的元素個數(shù)，p 為誤報率。

應(yīng)用場景

• HTTP緩存服務(wù)器、Web爬蟲等

主要工作是判斷一條URL是否在現(xiàn)有的URL集合之中（可以認(rèn)為這里的數(shù)據(jù)量級上億）。

對于HTTP緩存服務(wù)器，當(dāng)本地局域網(wǎng)中的PC發(fā)起一條HTTP請求時，緩存服務(wù)器會先查看一下這個URL是否已經(jīng)存在于緩存之中，如果存在的話就沒有必要去原始的服務(wù)器拉取數(shù)據(jù)了，這樣既能節(jié)省流量，還能加快訪問速度，以提高用戶體驗。

對于Web爬蟲，要判斷當(dāng)前正在處理的網(wǎng)頁是否已經(jīng)處理過了，同樣需要當(dāng)前URL是否存在于已經(jīng)處理過的URL列表之中。

• 垃圾郵件過濾

假設(shè)郵件服務(wù)器通過發(fā)送方的郵件域或者IP地址對垃圾郵件進(jìn)行過濾，那么就需要判斷當(dāng)前的郵件域或者IP地址是否處于黑名單之中。如果郵件服務(wù)器的通信郵件數(shù)量非常大（也可以認(rèn)為數(shù)據(jù)量級上億），那么也可以使用Bloom Filter算法。

JAVA實現(xiàn)布隆過濾器

先實現(xiàn)一個簡單的布隆過濾器

這段代碼是構(gòu)建了一個10億位的bitSet，然后把一億個userId加入到了我們的布隆過濾器中，最近判斷5324512515這個userId是否登錄，打出代碼的執(zhí)行時間