布隆過(guò)濾器
- 作者: 博學(xué)谷狂野架構(gòu)師
- GitHub：GitHub地址 （有我精心準(zhǔn)備的130本電子書(shū)PDF）
只分享干貨、不吹水八秃，讓我們一起加油碱妆！??
什么是布隆過(guò)濾器
布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多扶叉，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難舶治。
布隆過(guò)濾器可以理解為一個(gè)不怎么精確的 set 結(jié)構(gòu)葱跋，當(dāng)你使用它的 contains 方法判斷某個(gè)對(duì)象是否存在時(shí)，它可能會(huì)誤判。但是布隆過(guò)濾器也不是特別不精確，只要參數(shù)設(shè)置的合理繁成，它的精確度可以控制的相對(duì)足夠精確，只會(huì)有小小的誤判概率淑玫。
當(dāng)布隆過(guò)濾器說(shuō)某個(gè)值存在時(shí)巾腕，這個(gè)值可能不存在；當(dāng)它說(shuō)不存在時(shí)絮蒿，那就肯定不存在尊搬。打個(gè)比方，當(dāng)它說(shuō)不認(rèn)識(shí)你時(shí)土涝，肯定就不認(rèn)識(shí)佛寿；當(dāng)它說(shuō)見(jiàn)過(guò)你時(shí)，可能根本就沒(méi)見(jiàn)過(guò)面但壮，不過(guò)因?yàn)槟愕哪樃J(rèn)識(shí)的人中某臉比較相似 (某些熟臉的系數(shù)組合)冀泻，所以誤判以前見(jiàn)過(guò)你。
套在上面的使用場(chǎng)景中茵肃，布隆過(guò)濾器能準(zhǔn)確過(guò)濾掉那些已經(jīng)看過(guò)的內(nèi)容，那些沒(méi)有看過(guò)的新內(nèi)容袭祟，它也會(huì)過(guò)濾掉極小一部分 (誤判)验残，但是絕大多數(shù)新內(nèi)容它都能準(zhǔn)確識(shí)別。這樣就可以完全保證推薦給用戶的內(nèi)容都是無(wú)重復(fù)的巾乳。
布隆過(guò)濾器的原理
其本質(zhì)就是一個(gè)只包含0和1的數(shù)組您没。具體操作當(dāng)一個(gè)元素被加入到集合里面后鸟召，該元素通過(guò)K個(gè)Hash函數(shù)運(yùn)算得到K個(gè)hash后的值，然后將K個(gè)值映射到這個(gè)位數(shù)組對(duì)應(yīng)的位置氨鹏，把對(duì)應(yīng)位置的值設(shè)置為1欧募。查詢是否存在時(shí)，我們就看對(duì)應(yīng)的映射點(diǎn)位置如果全是1仆抵，他就很可能存在（跟hash函數(shù)的個(gè)數(shù)和hash函數(shù)的設(shè)計(jì)有關(guān)）跟继，如果有一個(gè)位置是0，那這個(gè)元素就一定不存在镣丑。
- 首先需要初始化一個(gè)二進(jìn)制的數(shù)組舔糖，長(zhǎng)度設(shè)為 L，同時(shí)初始值全為 0 莺匠。
- 當(dāng)寫(xiě)入一個(gè) A1=1000 的數(shù)據(jù)時(shí)金吗，需要進(jìn)行 H 次 hash 函數(shù)的運(yùn)算（這里為 2 次）；與 HashMap 有點(diǎn)類(lèi)似趣竣，通過(guò)算出的 HashCode 與 L 取模后定位到 0摇庙、2 處，將該處的值設(shè)為 1遥缕。
- A2=2000 也是同理計(jì)算后將 4卫袒、7 位置設(shè)為 1。
- 當(dāng)有一個(gè) B1=1000 需要判斷是否存在時(shí)通砍，也是做兩次 Hash 運(yùn)算玛臂，定位到 0、2 處封孙，此時(shí)他們的值都為 1 迹冤，所以認(rèn)為 B1=1000 存在于集合中。
- 當(dāng)有一個(gè) B2=3000 時(shí)虎忌，也是同理泡徙。第一次 Hash 定位到 index=4 時(shí)，數(shù)組中的值為 1膜蠢，所以再進(jìn)行第二次 Hash 運(yùn)算堪藐，結(jié)果定位到 index=5 的值為 0，所以認(rèn)為 B2=3000 不存在于集合中挑围。
整個(gè)的寫(xiě)入礁竞、查詢的流程就是這樣，匯總起來(lái)就是：
對(duì)寫(xiě)入的數(shù)據(jù)做 H 次 hash 運(yùn)算定位到數(shù)組中的位置杉辙，同時(shí)將數(shù)據(jù)改為 1 模捂。當(dāng)有數(shù)據(jù)查詢時(shí)也是同樣的方式定位到數(shù)組中。一旦其中的有一位為 0 則認(rèn)為數(shù)據(jù)肯定不存在于集合，否則數(shù)據(jù)可能存在于集合中狂男。
布隆過(guò)濾器的特點(diǎn)
只要返回?cái)?shù)據(jù)不存在综看，則肯定不存在。
返回?cái)?shù)據(jù)存在岖食，但只能是大概率存在红碑。
同時(shí)不能清除其中的數(shù)據(jù)。
在有限的數(shù)組長(zhǎng)度中存放大量的數(shù)據(jù)泡垃，即便是再完美的 Hash 算法也會(huì)有沖突析珊，所以有可能兩個(gè)完全不同的 A、B 兩個(gè)數(shù)據(jù)最后定位到的位置是一模一樣的兔毙。
刪除數(shù)據(jù)也是同理唾琼，當(dāng)我把 B 的數(shù)據(jù)刪除時(shí)，其實(shí)也相當(dāng)于是把 A 的數(shù)據(jù)刪掉了澎剥，這樣也會(huì)造成后續(xù)的誤報(bào)锡溯。
基于以上的 Hash 沖突的前提，所以 Bloom Filter 有一定的誤報(bào)率哑姚，這個(gè)誤報(bào)率和 Hash 算法的次數(shù) H祭饭，以及數(shù)組長(zhǎng)度 L 都是有關(guān)的。
應(yīng)用場(chǎng)景
緩存穿透
我們經(jīng)常會(huì)把一部分?jǐn)?shù)據(jù)放在Redis等緩存叙量，比如產(chǎn)品詳情倡蝙。這樣有查詢請(qǐng)求進(jìn)來(lái)，我們可以根據(jù)產(chǎn)品Id直接去緩存中取數(shù)據(jù)绞佩，而不用讀取數(shù)據(jù)庫(kù)寺鸥，這是提升性能最簡(jiǎn)單，最普遍品山，也是最有效的做法胆建。一般的查詢請(qǐng)求流程是這樣的：先查緩存，有緩存的話直接返回肘交，如果緩存中沒(méi)有笆载，再去數(shù)據(jù)庫(kù)查詢，然后再把數(shù)據(jù)庫(kù)取出來(lái)的數(shù)據(jù)放入緩存涯呻，一切看起來(lái)很美好凉驻。但是如果現(xiàn)在有大量請(qǐng)求進(jìn)來(lái)，而且都在請(qǐng)求一個(gè)不存在的產(chǎn)品Id复罐，會(huì)發(fā)生什么涝登？既然產(chǎn)品Id都不存在，那么肯定沒(méi)有緩存效诅，沒(méi)有緩存胀滚，那么大量的請(qǐng)求都懟到數(shù)據(jù)庫(kù)咳短，數(shù)據(jù)庫(kù)的壓力一下子就上來(lái)了，還有可能把數(shù)據(jù)庫(kù)打死蛛淋。
使用布隆過(guò)濾器的特點(diǎn)，只要返回?cái)?shù)據(jù)不存在篡腌，則肯定不存在褐荷，返回?cái)?shù)據(jù)存在，但只能是大概率存在嘹悼，這種特點(diǎn)可以大批量的無(wú)效請(qǐng)求過(guò)濾掉叛甫，能夠穿透緩存的知識(shí)漏網(wǎng)之魚(yú)，無(wú)關(guān)緊要杨伙。
檢查單詞拼寫(xiě)
檢查一個(gè)單詞拼寫(xiě)是否正確其监，因?yàn)橛泻Ａ康膯卧~數(shù)量，每天可能有新的單詞限匣，使用布隆過(guò)濾器抖苦，可以將單詞映射到很小的內(nèi)存中，可以經(jīng)過(guò)簡(jiǎn)單的幾次hash運(yùn)行就可以進(jìn)行校驗(yàn)米死，只要返回?cái)?shù)據(jù)不存在锌历，則肯定不存在，返回?cái)?shù)據(jù)存在峦筒，但只能是大概率存在究西，雖然可能有誤報(bào)，但是對(duì)系統(tǒng)的提升是革命性的物喷。
Guava的布隆過(guò)濾器
這就又要提起我們的Guava了卤材，它是Google開(kāi)源的Java包，提供了很多常用的功能峦失。
Guava中扇丛，布隆過(guò)濾器的實(shí)現(xiàn)主要涉及到2個(gè)類(lèi)，BloomFilter和BloomFilterStrategies宠进，首先來(lái)看一下BloomFilter的成員變量晕拆。需要注意的是不同Guava版本的BloomFilter實(shí)現(xiàn)不同。
布隆過(guò)濾器解析
成員變量分析
COPY/** guava實(shí)現(xiàn)的以CAS方式設(shè)置每個(gè)bit位的bit數(shù)組 */
private final LockFreeBitArray bits;
/** hash函數(shù)的個(gè)數(shù) */
private final int numHashFunctions;
/** guava中將對(duì)象轉(zhuǎn)換為byte的通道 */
private final Funnel<? super T> funnel;
/**
* 將byte轉(zhuǎn)換為n個(gè)bit的策略材蹬，也是bloomfilter hash映射的具體實(shí)現(xiàn)
*/
private final Strategy strategy;
這是它的4個(gè)成員變量:
LockFreeBitArray是定義在
BloomFilterStrategies中的內(nèi)部類(lèi)实幕，封裝了布隆過(guò)濾器底層bit數(shù)組的操作。numHashFunctions表示哈希函數(shù)的個(gè)數(shù)堤器。
Funnel昆庇，它和PrimitiveSink配套使用，能將任意類(lèi)型的對(duì)象轉(zhuǎn)化成Java基本數(shù)據(jù)類(lèi)型闸溃，默認(rèn)用java.nio.ByteBuffer實(shí)現(xiàn)整吆，最終均轉(zhuǎn)化為byte數(shù)組拱撵。
-
Strategy是定義在BloomFilter類(lèi)內(nèi)部的接口，代碼如下表蝙，主要有2個(gè)方法拴测，put和mightContain。
COPYinterface Strategy extends java.io.Serializable { /** 設(shè)置元素 */ <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits); /** 判斷元素是否存在*/ <T> boolean mightContain( T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits); ..... }
創(chuàng)建布隆過(guò)濾器府蛇，BloomFilter并沒(méi)有公有的構(gòu)造函數(shù)集索，只有一個(gè)私有構(gòu)造函數(shù)，而對(duì)外它提供了5個(gè)重載的create方法汇跨，在缺省情況下誤判率設(shè)定為3%务荆，采用BloomFilterStrategies.MURMUR128_MITZ_64的實(shí)現(xiàn)。
BloomFilterStrategies.MURMUR128_MITZ_64是Strategy的兩個(gè)實(shí)現(xiàn)之一穷遂，Guava以枚舉的方式提供這兩個(gè)實(shí)現(xiàn)函匕，這也是《Effective Java》書(shū)中推薦的提供對(duì)象的方法之一。
COPYenum BloomFilterStrategies implements BloomFilter.Strategy {
MURMUR128_MITZ_32() {//....}
MURMUR128_MITZ_64() {//....}
}
二者對(duì)應(yīng)了32位哈希映射函數(shù)蚪黑，和64位哈希映射函數(shù)盅惜，后者使用了murmur3 hash生成的所有128位，具有更大的空間忌穿，不過(guò)原理是相通的酷窥，我們選擇相對(duì)簡(jiǎn)單的MURMUR128_MITZ_32來(lái)分析。
先來(lái)看一下它的put方法伴网，它用兩個(gè)hash函數(shù)來(lái)模擬多個(gè)hash函數(shù)的情況蓬推，這是布隆過(guò)濾器的一種優(yōu)化。
put方法
COPYpublic <T> boolean put(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
long bitSize = bits.bitSize();
// 先利用murmur3 hash對(duì)輸入的funnel計(jì)算得到128位的哈希值澡腾，funnel現(xiàn)將object轉(zhuǎn)換為byte數(shù)組沸伏，
// 然后在使用哈希函數(shù)轉(zhuǎn)換為long
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
// 根據(jù)hash值的高低位算出hash1和hash2
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
boolean bitsChanged = false;
// 循環(huán)體內(nèi)采用了2個(gè)函數(shù)模擬其他函數(shù)的思想,相當(dāng)于每次累加hash2
for (int i = 1; i <= numHashFunctions; i++) {
int combinedHash = hash1 + (i * hash2);
// 如果是負(fù)數(shù)就變?yōu)檎龜?shù)
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 通過(guò)基于bitSize取模的方式獲取bit數(shù)組中的索引，然后調(diào)用set函數(shù)設(shè)置动分。
bitsChanged |= bits.set(combinedHash % bitSize);
}
return bitsChanged;
}
在put方法中毅糟，先是將索引位置上的二進(jìn)制置為1，然后用bitsChanged記錄插入結(jié)果澜公，如果返回true表明沒(méi)有重復(fù)插入成功姆另，而mightContain方法則是將索引位置上的數(shù)值取出，并判斷是否為0坟乾，只要其中出現(xiàn)一個(gè)0迹辐，那么立即判斷為不存在。
mightContain方法
COPYpublic <T> boolean mightContain(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
long bitSize = bits.bitSize();
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int combinedHash = hash1 + (i * hash2);
// Flip all the bits if it's negative (guaranteed positive number)
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 和put的區(qū)別就在這里甚侣，從set轉(zhuǎn)換為get明吩，來(lái)判斷是否存在
if (!bits.get(combinedHash % bitSize)) {
return false;
}
}
return true;
}
Guava為了提供效率，自己實(shí)現(xiàn)了LockFreeBitArray來(lái)提供bit數(shù)組的無(wú)鎖設(shè)置和讀取殷费。我們只來(lái)看一下它的put函數(shù)印荔。
COPYboolean set(long bitIndex) {
if (get(bitIndex)) {
return false;
}
int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex
long oldValue;
long newValue;
// 經(jīng)典的CAS自旋重試機(jī)制
do {
oldValue = data.get(longIndex);
newValue = oldValue | mask;
if (oldValue == newValue) {
return false;
}
} while (!data.compareAndSet(longIndex, oldValue, newValue));
bitCount.increment();
return true;
}
Guava布隆過(guò)濾器使用
引入坐標(biāo)
COPY<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
代碼實(shí)現(xiàn)
COPY
public class GuavaBloomFilter {
/**
* 設(shè)置布隆過(guò)濾器大小
*/
private static final int size = 100000;
/**
* 構(gòu)建一個(gè)BloomFilter
* 第一個(gè)參數(shù)Funnel類(lèi)型的參數(shù)
* 第二個(gè)參數(shù) 期望處理的數(shù)據(jù)量
* 第三個(gè)參數(shù) 誤判率 可不加低葫，默認(rèn) 0.03D
*/
private static final BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), size);
public static void main(String[] args) {
//成功計(jì)數(shù)
float success = 0;
//失敗計(jì)數(shù)
float fial = 0;
Set<String> stringSet = new HashSet<String>();
for (int i = 0; i < size; i++) {
//生成隨機(jī)字符串
String randomStr = RandomStringUtils.randomNumeric(10);
//加入到set中
stringSet.add(randomStr);
//加入到布隆過(guò)濾器
bloomFilter.put(randomStr);
}
for (int i = 0; i < size; i++) {
//生成隨機(jī)字符串
String randomStr = RandomStringUtils.randomNumeric(10);
//布隆過(guò)濾器校驗(yàn)存在
if (bloomFilter.mightContain(randomStr)) {
//set中存在
if (stringSet.contains(randomStr)) {
//成功計(jì)數(shù)
success++;
} else {
//失敗計(jì)數(shù)
fial++;
}
//布隆過(guò)濾器校驗(yàn)不存在
} else {
// set中存在
if (stringSet.contains(randomStr)) {
//失敗計(jì)數(shù)
fial++;
} else {
//成功計(jì)數(shù)
success++;
}
}
}
System.out.println("判斷成功數(shù)："+success + "仍律，判斷失敗數(shù):" + fial + "，誤判率:" + fial / 100000);
}
輸出
COPY判斷成功數(shù)：97084.0水泉，判斷失敗數(shù):2916.0，誤判率:0.02916
可以通過(guò)增加誤判率的參數(shù)來(lái)調(diào)整誤判率
COPY/**
* 構(gòu)建一個(gè)BloomFilter
* 第一個(gè)參數(shù)Funnel類(lèi)型的參數(shù)
* 第二個(gè)參數(shù) 期望處理的數(shù)據(jù)量
* 第三個(gè)參數(shù) 誤判率 可不加茶行，默認(rèn) 0.03D
*/
private static final BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), size,0.00001);
輸出
COPY判斷成功數(shù)：100000.0，判斷失敗數(shù):0.0登钥，誤判率:0.0
本文由
傳智教育博學(xué)谷狂野架構(gòu)師教研團(tuán)隊(duì)發(fā)布。如果本文對(duì)您有幫助牧牢，歡迎
關(guān)注和點(diǎn)贊；如果您有任何建議也可留言評(píng)論或私信塔鳍，您的支持是我堅(jiān)持創(chuàng)作的動(dòng)力伯铣。轉(zhuǎn)載請(qǐng)注明出處！
