大白話講解布隆過濾器（BloomFilter）
閱讀大概需要4
JavaPub說
關(guān)于布隆過濾器
1.1.基礎(chǔ)介紹
1.1.1.百度百科
1.1.2.原理介紹
1.1.3.布隆過濾器的屬性
1.2.數(shù)學(xué)推導(dǎo)
1.3.哈希
2.1.Java版
3.1.進(jìn)階一(參數(shù)定義)
3.1.1.介紹
3.1.2.Java實(shí)現(xiàn)
3.2.進(jìn)階二(redis版)
3.2.1.介紹
3.2.2.Java代碼
前言
聲明：參考來源互聯(lián)網(wǎng)，有任何爭(zhēng)議可以留言。站在前人的肩上，我們才能看的更遠(yuǎn)。
本教程純手打，致力于最實(shí)用教程，不需要什么獎(jiǎng)勵(lì)，只希望多多轉(zhuǎn)發(fā)支持。 歡迎來我公眾號(hào)，希望可以結(jié)識(shí)你，也可以催更，微信搜索：JavaPub
有任何問題都可以來談?wù)?，等你?/p>
JavaPub說
布隆大家都知道吧，如果不知道沒關(guān)系，介紹一下，E技能，堅(jiān)不可摧
堅(jiān)不可摧 E 消耗法力：30/35/40/45/50冷卻時(shí)間：18/16/14/12/10 布隆朝一個(gè)方向舉起盾牌，持續(xù)3/3.25/3.5/3.75/4秒，并使來自目標(biāo)
回憶完以上，下面繼續(xù)
關(guān)于布隆過濾器
布隆過濾器主要用來做去重操作。在對(duì)準(zhǔn)確率要求不高的業(yè)務(wù)場(chǎng)景使用廣泛。
布隆過濾器的核心是：如果計(jì)算出有一個(gè)元素已存在，那么它可能存在，如果一個(gè)元素不存在，那么它一定不存在。
簡(jiǎn)單來說，寧錯(cuò)殺三千，不放過一個(gè)。
例如：長(zhǎng)城防火墻有100億個(gè)需要屏蔽的網(wǎng)站，計(jì)算機(jī)的每次請(qǐng)求都要經(jīng)過防火墻的過濾判斷請(qǐng)求URL是否在黑名單中，如果我們使用HashSet來實(shí)現(xiàn)過濾的話，我們假設(shè)每個(gè)URL的大小為64B，那么100億個(gè)就至少需要大約640GB的內(nèi)存空間，這顯然是不符合實(shí)際情況的。
到目前我使用比較多的是在數(shù)據(jù)采集中，url去重，郵箱中的垃圾郵件過濾等。
1.介紹
1.1.基礎(chǔ)介紹
1.1.1.百度百科
百度百科：布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
1.1.2.原理介紹
布隆過濾器的原理和哈希表的原理有點(diǎn)類似，同樣需要使用hash函數(shù)，但是在布隆過濾器中，需要使用多個(gè)hash函數(shù)。布隆過濾器的原理還是比較簡(jiǎn)單的。
我們有一個(gè)位數(shù)組bitArray，假設(shè)長(zhǎng)度為m，就是只存0、1那種。此時(shí)有個(gè)key，和n個(gè)hash函數(shù)，可以得到n個(gè)key被hash過后的數(shù)。我們分別取hash對(duì)應(yīng)bitArray中位置的值，置位1。
如圖 {x,y,z} 是一個(gè)集合，通過三次hash計(jì)算，映射對(duì)應(yīng)的值到 位數(shù)組 對(duì)應(yīng)位置。當(dāng)我們要求 w 是否存在時(shí)，只要對(duì)w計(jì)算hash，再找對(duì)應(yīng)位置是否為1即可。但是，也有可能正好hash值對(duì)應(yīng)的 位數(shù)組 位置都為1，這個(gè)概念叫做誤算率。實(shí)際上，這就和哈希表中哈希沖突的情況一樣，因?yàn)榭赡軙?huì)出現(xiàn)兩個(gè)key值經(jīng)過k個(gè)hash函數(shù)之后，取余之后的結(jié)果是一樣的。
1.1.3.布隆過濾器的屬性
如果布隆過濾器判斷數(shù)據(jù)不存在則數(shù)據(jù)絕對(duì)不存在。
這個(gè)就是布隆過濾器的特點(diǎn)，數(shù)據(jù)先經(jīng)過布隆過濾器，查詢數(shù)據(jù)是否已經(jīng)存在。如果布隆過濾器判斷用戶名不存在/或者存在，數(shù)據(jù)才能夠繼續(xù)向下走。
在前面的判斷中，可以判斷數(shù)據(jù)絕對(duì)不存在，但是如果判斷數(shù)據(jù)存在，則數(shù)據(jù)也可能不存在。
布隆過濾器只能插入數(shù)據(jù)，而不能刪除數(shù)據(jù)。
1.2.數(shù)學(xué)推導(dǎo)
既然誤算率一定存在，當(dāng)然我們想減小誤判到最小（key數(shù)量和bitArray長(zhǎng)度確定）。
數(shù)學(xué)公式
1.3.哈希
讀到這里我們對(duì)布隆過濾器有了一定了解，hash函數(shù)對(duì) 布隆過濾器 的優(yōu)劣起了決定性作用。
Hash參考百度百科：https://baike.baidu.com/item/hash/390310
目標(biāo)就是設(shè)計(jì)一種盡可能少碰撞的hash算法，盡可能讓它平均分布到每一位。
2.基礎(chǔ)用法
2.1.Java版
下面是一篇簡(jiǎn)單版本的布隆過濾器，使用了 java.util.BitSet
package?com.javapub.cache;
import?java.util.BitSet;
/**
?*?@author?wangshiyu?rodert?JavaPub
?*?@date?2020/5/26?15:23
?*?@description?一篇簡(jiǎn)單的布隆過濾器
?*/
public?class?BloomFilterSimple?{
????private?static?final?int?SIZE?=?1?<<?24;
????private?static?BitSet?bitSet?=?new?BitSet(SIZE);
????private?static?Hash[]?hashes?=?new?Hash[5];
????private?static?final?int?seeds[]?=?new?int[]{3,?5,?7,?9,?11};
????static?{
????????init();
????}
????private?static?void?init()?{
????????for?(int?i?=?0;?i?<?seeds.length;?i++)?{
????????????hashes[i]?=?new?Hash(seeds[i]);
????????}
????}
????private?boolean?add(String?data)?{
????????for?(Hash?hash?:?hashes)?{
????????????int?hashCode?=?hash.getHash(data);
????????????bitSet.set(hashCode,?true);
????????}
????????return?true;
????}
????private?boolean?contains(String?data)?{
????????boolean?have?=?true;
????????for?(Hash?hash?:?hashes)?{
????????????have?&=?bitSet.get(hash.getHash(data));
????????}
????????return?have;
????}
????/**
?????*?如果不存在就進(jìn)行記錄并返回false，如果存在了就返回true
?????*
?????*?@param?data
?????*?@return
?????*/
????private?boolean?addIfNotExist(String?data)?{
????????boolean?contains?=?contains(data);
????????if?(contains)?{
????????????return?true;
????????}?else?{
????????????add(data);
????????????return?false;
????????}
????}
????public?static?void?main(String[]?args)?{
????????String?data?=?"https://gitee.com/rodert";
????????String?data2?=?"https://gitee.com/rodert/JavaPub";
????????BloomFilterSimple?bloomFilterSimple?=?new?BloomFilterSimple();
????????System.out.println(bloomFilterSimple.add(data));
????????System.out.println(bloomFilterSimple.contains(data));
????????System.out.println(bloomFilterSimple.addIfNotExist(data2));
????????System.out.println(bloomFilterSimple.contains(data2));
????????System.out.println(bitSet);
????}
????private?static?class?Hash?{
????????private?int?seed?=?0;
????????private?Hash(int?seed)?{
????????????this.seed?=?seed;
????????}
????????private?int?getHash(String?string)?{
????????????int?val?=?0;
????????????int?len?=?string.length();
????????????for?(int?i?=?0;?i?<?len;?i++)?{
????????????????val?=?val?*?seed?+?string.charAt(i);
????????????}
????????????return?val?&?(SIZE?-?1);
????????}
????}
}
3.進(jìn)階
3.1.進(jìn)階一(參數(shù)定義)
3.1.1.介紹
如果你有興趣了解更多，我們繼續(xù)往下看
前面寫了一個(gè)簡(jiǎn)單的DEMO，位數(shù)組長(zhǎng)度和誤差率都是拍腦袋定的，這篇主要講解如何定義合適的位數(shù)組長(zhǎng)度，計(jì)算方式
1.1.2.原理介紹
我們有一個(gè)位數(shù)組bitArray，假設(shè)長(zhǎng)度為m，就是只存0、1那種。此時(shí)有個(gè)key，和k個(gè)hash函數(shù)，可以得到k個(gè)key被hash過后的數(shù)。我們分別取hash對(duì)應(yīng)bitArray中位置的值，置位1。
如圖 {x,y,z} 是一個(gè)集合，通過三次hash計(jì)算，映射對(duì)應(yīng)的值到 位數(shù)組 對(duì)應(yīng)位置。當(dāng)我們要求 w 是否存在時(shí)，只要對(duì)w計(jì)算hash，再找對(duì)應(yīng)位置是否為1即可。但是，也有可能正好hash值對(duì)應(yīng)的 位數(shù)組 位置都為1，這個(gè)概念叫做誤算率。實(shí)際上，這就和哈希表中哈希沖突的情況一樣，因?yàn)榭赡軙?huì)出現(xiàn)兩個(gè)key值經(jīng)過k個(gè)hash函數(shù)之后，取余之后的結(jié)果是一樣的。
上面是我們?cè)谠斫榻B講到的，綜上所述，我們需要多少個(gè)哈希函數(shù)，創(chuàng)建多長(zhǎng)的bit數(shù)組比較合適，為了估算出k和m的值，在構(gòu)造一個(gè)布隆過濾器時(shí)，需要傳入兩個(gè)參數(shù)，即可以接受的誤判率fpp和元素總個(gè)數(shù)n（不一定完全精確）。至于參數(shù)估計(jì)的方法，有興趣的同學(xué)可以參考維基英文頁(yè)面，下面直接給出公式：
哈希函數(shù)的要求盡量滿足平均分布，這樣既降低誤判發(fā)生的概率，又可以充分利用bit數(shù)組的空間；
根據(jù)論文《Less Hashing, Same Performance: Building a Better Bloom Filter》提出的一個(gè)技巧，可以用2個(gè)哈希函數(shù)來模擬k個(gè)哈希函數(shù)，即gi(x) = h1(x) + ih2(x) ，其中0<=i<=k-1；
在吳軍博士的《數(shù)學(xué)之美》一書中展示了不同情況下的誤判率，例如，假定一個(gè)元素用16位比特，8個(gè)哈希函數(shù)，那么假陽(yáng)性的概率是萬(wàn)分之五，這已經(jīng)相當(dāng)小了。
3.1.2.Java實(shí)現(xiàn)
計(jì)算 位數(shù)組長(zhǎng)度
n是準(zhǔn)備存入數(shù)據(jù)數(shù)量，p是誤判率。
public?static?long?optimalNumOfBits(long?n,?double?p)?{
????return?(long)((double)(-n)?*?Math.log(p)?/?(Math.log(2.0D)?*?Math.log(2.0D)));
}
計(jì)算hash函數(shù)個(gè)數(shù)
n是準(zhǔn)備存入數(shù)據(jù)數(shù)量，m是bit數(shù)組長(zhǎng)度。
public?static?int?optimalNumOfHashFunctions(long?n,?long?m)?{
????return?Math.max(1,?(int)Math.round((double)m?/?(double)n?*?Math.log(2.0D)));
}
3.2.進(jìn)階二(redis版)
3.2.1.介紹
布隆過濾器自提出以后，很多開源工具中都對(duì)它進(jìn)行了實(shí)現(xiàn)。如 Google 的 Guava 中。
對(duì)于現(xiàn)在大趨勢(shì)分布式架構(gòu)，單機(jī)存到緩存肯定是適用場(chǎng)景有限，so，我們借助 redis。
redis 數(shù)據(jù)類型 bit ，用法和上邊一樣，這里主要說關(guān)于動(dòng)態(tài)擴(kuò)容。
擴(kuò)容的核心就是在每次插入前判斷當(dāng)前 位數(shù)組 為1(jedis.bitcount)的個(gè)數(shù)比(/) 位數(shù)組總長(zhǎng)度，超過50%，那么就新建一個(gè) bit，布隆過濾器的核心思想。判斷一個(gè)元素是否在集合中？可能在集合中 和 絕對(duì)不在集合中
3.2.2.Java代碼
由于篇幅過長(zhǎng)，后面會(huì)在公眾號(hào)單獨(dú)發(fā)出
擴(kuò)展閱讀
布隆過濾器換包含：并行分區(qū)的布隆過濾器、穩(wěn)定的布隆過濾器、可擴(kuò)展的Bloom過濾器、空間布隆過濾器、衰減的布隆過濾器等。
更多閱讀閱讀維基百科英文：https://en.wikipedia.org/wiki/Bloom_filter
