布隆過濾器（Bloom Filter）是一個叫做 Bloom 的大佬在1970年提出的。我們可以把它看做由二進(jìn)制向量（或者說數(shù)組）和一系列隨機(jī)映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結(jié)構(gòu)。相比于我們平時用的 List，Set，Map 等容器，它占用的空間更少且效率更高，但缺點是其返回的結(jié)果是概率性的，而不是非常準(zhǔn)確的。理論情況下添加到集合中的元素越多，誤報的可能性就越大。并且，存放在布隆過濾器的數(shù)據(jù)不容易刪除。

它的基本思想是：當(dāng)一個元素被加入集合時，通過 K 個散列函數(shù)將這個元素映射成一個位數(shù)組中的 K 個點，把它們置為1；檢索時，只要看看這些點是不是都是1 就（大約）知道集合中有沒有它了——如果這些點有任何一個0，則被檢元素一定不在，如果都是1，則被檢元素很可能在。

1.原理

布隆過濾器（Bloom Filter）核心實現(xiàn)是一個超大的位數(shù)組和幾個哈希函數(shù)。如下圖所示，有一個大小為 12 的數(shù)組，然后有3個哈希函數(shù)：

1.1 流程分析

假如現(xiàn)在有一個 keyword 要放入某個容器了，現(xiàn)在要經(jīng)過Bloom Filter，具體的操作流程如下：

過濾器初始化：將位數(shù)組進(jìn)行初始化，即數(shù)組每位都設(shè)置位0

放入元素：

對于集合里面的每一個元素，將元素依次通過3個哈希函數(shù)進(jìn)行映射，每次映射都會產(chǎn)生一個哈希值

每個計算得到的哈希值對應(yīng)位數(shù)組上面的一個點，所以將位數(shù)組對應(yīng)的位置標(biāo)記為1

判斷存在：查詢W元素是否存在集合中的時候，同樣的方法將W通過哈希映射到位數(shù)組上的3個點

• 如果3個點的其中有一個點不為1，則可以判斷該元素一定不存在集合中
• 如果3個點都為1，則該元素可能存在集合中

因為此處不能判斷該元素是否一定存在集合中，可能存在一定的誤判率。

1.2 誤差分析

可以從圖中可以看到，向容器中 put 時，x1映射到（2/4/8）,x2映射到（4/6/10）：

假設(shè)現(xiàn)在要判斷元素 W 是否在容器中，通過哈希函數(shù)計算出的結(jié)果是（4/6/8），雖然指定位都為1，但顯然沒有這個元素。因此這種情況說明元素雖然不在集合中，也可能對應(yīng)的都是1，這是誤判率存在的原因。

2.應(yīng)用場景

在很多場景下，我們都需要一個能迅速判斷一個元素是否在一個集合中。譬如：

網(wǎng)頁爬蟲對URL的去重，避免爬取相同的URL地址

反垃圾郵件，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱（同理，垃圾短信）

緩存擊穿，將已存在的緩存放到布隆中，當(dāng)黑客訪問不存在的緩存時迅速返回避免緩存及DB掛掉

問題：

可能有人會問，我們直接把這些數(shù)據(jù)都放到數(shù)據(jù)庫或者redis之類的緩存中不就行了，查詢時直接匹配不就OK了？

是的，當(dāng)這個集合量比較小，你內(nèi)存又夠大時，是可以這樣做，你可以直接弄個HashSet、HashMap就OK了。但是當(dāng)這個量以數(shù)十億計，內(nèi)存裝不下，數(shù)據(jù)庫檢索極慢時該怎么辦。

4種解決方案：

將所有垃圾郵箱地址存到數(shù)據(jù)庫，匹配時遍歷

用HashSet存儲所有地址，匹配時接近O（1）的效率查出來

將地址用MD5算法或其他單向映射算法計算后存入HashSet，無論地址多大，保存的只有MD5后的固定位數(shù)

布隆過濾器，將所有地址經(jīng)過多個Hash算法，映射到一個bit數(shù)組

4種方案優(yōu)劣：

方案1，因為是保存完整的地址，占用空間大。一個地址16字節(jié)，10億即可達(dá)到上百G的內(nèi)存。而且數(shù)據(jù)庫的查詢效率也比不上HashSet等數(shù)據(jù)結(jié)構(gòu)

方案2，雖然HashSet效率逼近O(1)，但底層HashMap的擴(kuò)容因子是0.75，也就是你想存75個數(shù)，至少需要一個100的數(shù)組，而且還會有不少的沖突。實際上，Hash的存儲效率是0.5左右，存5個數(shù)需要10個的空間。算起來占用空間還是挺大的

方案3，因為保存部分信息，所以占用空間小于存儲完整信息，但仍然存在沖突的可能（非垃圾郵箱可能MD5后和某垃圾郵箱一樣，概率低）

方案4，將所有地址經(jīng)過Hash后映射到同一個bit數(shù)組，因為只有一個超大的bit數(shù)組，保存所有的映射，占用空間極小，沖突概率高。只要概率在可以接受的范圍，用時間換空間

可以看到，每種方案都有自己的不足之處，所以一定要根據(jù)數(shù)據(jù)規(guī)模和業(yè)務(wù)需求來確定到底使用什么。

3.BloomFilter 代碼實現(xiàn)

下面就直接貼代碼，注釋已經(jīng)寫得很詳細(xì)了，而且布隆過濾器的邏輯本身就不復(fù)雜，應(yīng)該還是比較容易理解的…

class BloomFilter{// 二進(jìn)制向量（數(shù)組）的位數(shù)，相當(dāng)于能存儲1000萬條url左右，誤報率為千萬分之一private static final int BIT_SIZE = 2 << 28 ;// 二進(jìn)制數(shù)組（2^28 byte）private BitSet bits = new BitSet(BIT_SIZE);// 用于生成信息指紋的8個隨機(jī)數(shù)，最好選取質(zhì)數(shù)（使同一算法產(chǎn)生8個不同hash函數(shù)）private static final int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61}; // 用于存儲具體的8個哈希對象（每個里面包含了不同結(jié)果的hash函數(shù)）private Hash[] func = new Hash[seeds.length];public BloomFilter(){// 構(gòu)造BloomFilter時生成這8個隨機(jī)哈希對象for(int i = 0; i < seeds.length; i++){func[i] = new Hash(BIT_SIZE, seeds[i]);}}/*** 操作一：向過濾器中添加字符串*/public void addValue(String value) { if(value != null){// 將字符串value哈希為8個或多個整數(shù)for(Hash f : func) //然后在這些整數(shù)的bit上變?yōu)?bits.set(f.hash(value), true); }} /*** 操作二：判斷字符串是否包含在布隆過濾器中*/public boolean contains(String value) { if(value == null) return false; boolean ret = true; // 將要比較的字符串重新以上述方法計算hash值，再與布隆過濾器比對for(Hash f : func)// 注：這里 && ret 很關(guān)鍵，若有false了則能保證結(jié)果一定是falseret = ret && bits.get(f.hash(value)); return ret; } /*** 隨機(jī)哈希值對象（靜態(tài)內(nèi)部類）*/public static class Hash{private int size; // 二進(jìn)制向量數(shù)組大小private int seed; // 隨機(jī)數(shù)種子public Hash(int cap, int seed){this.size = cap;this.seed = seed;}/*** 計算哈希值(也可以選用別的恰當(dāng)?shù)墓：瘮?shù))*/public int hash(String value){int result = 0;int len = value.length();// 具體Hash算法：加權(quán)求和！！！for(int i = 0; i < len; i++){result = seed * result + value.charAt(i);}// 注：取模，得到具體二進(jìn)制數(shù)組下標(biāo)（result%（size-1））return (size - 1) & result;}} } public class Test {public static void main(String[] args){BloomFilter b = new BloomFilter();b.addValue("www.baidu.com");b.addValue("www.sohu.com");System.out.println(b.contains("www.baidu.com"));System.out.println(b.contains("www.sina.com"));} }

4.Guava自帶BloomFilter

除了自己實現(xiàn)BloomFilter，還可以直接使用guava包自帶的布隆過濾器。

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency>

下面是BloomFilter+redis的一個示例，目的是防止緩存穿透：

import com.google.common.hash.BloomFilter;// 初始化布隆過濾器 // 1000：期望存入的數(shù)據(jù)個數(shù)，0.001：期望的誤差率 BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf‐8")), 1000, 0.001);//把所有數(shù)據(jù)存入布隆過濾器 void init(){ for (String key: keys) { bloomFilter.put(key); } }String get(String key) { 1// 從布隆過濾器這一級緩存判斷下key是否存在 Boolean exist = bloomFilter.mightContain(key); if(!exist){ return ""; } // 從緩存中獲取數(shù)據(jù) String cacheValue = cache.get(key); // 緩存為空 if (StringUtils.isBlank(cacheValue)) { // 從存儲中獲取 String storageValue = storage.get(key); cache.set(key, storageValue); // 如果存儲數(shù)據(jù)為空， 需要設(shè)置一個過期時間(300秒) if (storageValue == null) { cache.expire(key, 60 * 5); } return storageValue; } else { // 緩存非空 return cacheValue; } }

總結(jié)

以上是生活随笔為你收集整理的【数据结构】布隆过滤器：BloomFilter原理及Java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。