布隆過(guò)濾器（Bloom Filter）
思考
如果要經(jīng)常判斷一個(gè)元素是否存在挟冠，是你的話携添，你會(huì)考慮怎么做？
- 很容易想到叛本，可以使用哈希表（HashSet沪蓬，HashMap）,將元素作為key來(lái)進(jìn)行查找
- 通過(guò)這種方法的時(shí)間復(fù)雜度為O(1)，但是缺點(diǎn)在于空間利用率不高来候，需要占用比較多的內(nèi)存資源
但是跷叉，如果要編寫(xiě)一個(gè)網(wǎng)絡(luò)爬蟲(chóng)去爬10億個(gè)網(wǎng)站數(shù)據(jù)，為了避免爬到重復(fù)的網(wǎng)站营搅，如何判斷某個(gè)網(wǎng)站是否爬過(guò)呢云挟？
- 很顯然，HashSet與HashMap比不是非常好的選擇转质，因?yàn)闀?huì)消耗大量的內(nèi)存空間
那是否存在時(shí)間復(fù)雜度低园欣，占用內(nèi)存空間少的方案？
布隆過(guò)濾器（Bloom Filter）就可以辦到這一點(diǎn)休蟹。
布隆過(guò)濾器簡(jiǎn)介
布隆過(guò)濾器是在1970年由布隆提出的沸枯，它是一個(gè)空間利用率高的概率型數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)告訴你鸡挠，一個(gè)元素一定不存在或者可能存在辉饱，基于這個(gè)結(jié)論，所以布隆過(guò)濾器有如下的優(yōu)缺點(diǎn)
- 優(yōu)點(diǎn)：空間效率和查詢(xún)時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法
- 缺點(diǎn)：有一定的誤判率拣展，刪除困難
雖然布隆過(guò)濾器存在一定的誤判率彭沼，但是誤判率依然可以通過(guò)代碼進(jìn)行控制，所以結(jié)合業(yè)務(wù)需求來(lái)進(jìn)行調(diào)整备埃。一般在如下情況下可以考慮使用布隆過(guò)濾器
- 經(jīng)常要判斷某一個(gè)元素是否存在
- 元素?cái)?shù)量巨大姓惑，希望有比較少的內(nèi)存空間
- 允許有一定的誤判率
本質(zhì)：布隆過(guò)濾器的本質(zhì)是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)（Hash函數(shù)）
通過(guò)上面的描述可以知道褐奴，布隆過(guò)濾器由2部分組成，一部分為哈希函數(shù)于毙，另外一部分為二進(jìn)制向量
二進(jìn)制向量：可以理解為二進(jìn)制數(shù)組
常見(jiàn)應(yīng)用
- 網(wǎng)頁(yè)黑名單系統(tǒng)敦冬，垃圾郵件過(guò)濾系統(tǒng)，爬蟲(chóng)的網(wǎng)址判重系統(tǒng)唯沮，解決緩存穿透問(wèn)題
布隆過(guò)濾器的原理
現(xiàn)假設(shè)布隆過(guò)濾器由20位二進(jìn)制（初始值為0）脖旱，3個(gè)哈希函數(shù)組成，每個(gè)元素經(jīng)過(guò)哈希函數(shù)處理都能生成一個(gè)索引
-
添加元素介蛉，將每一個(gè)哈希函數(shù)生成的索引萌庆，都設(shè)置為1
例如：現(xiàn)在假設(shè)要添加一個(gè)元素A，這會(huì)分別利用三個(gè)哈希函數(shù)币旧，生成對(duì)應(yīng)的所用值（假設(shè)第一個(gè)哈希函數(shù)生成的索引為4践险，第二個(gè)哈希函數(shù)生成的索引為7，第三個(gè)哈希函數(shù)生成的索引為18）吹菱，然后將數(shù)組中的對(duì)應(yīng)索引中的值設(shè)置為1
如果要繼續(xù)添加元素B巍虫，同樣會(huì)利用三個(gè)哈希函數(shù)，生成對(duì)應(yīng)的索引值（假設(shè)第一個(gè)哈希函數(shù)生成的索引值為2鳍刷，第二個(gè)哈希函數(shù)生成的索引值為7占遥，第三個(gè)哈希函數(shù)生成的索引值為15），然后將數(shù)組中的對(duì)應(yīng)索引中的值設(shè)置為1
- 查詢(xún)?cè)厥欠翊嬖冢?br>
利用哈希函數(shù)倾剿，分別計(jì)算出元素在對(duì)應(yīng)函數(shù)下的索引筷频，如果對(duì)應(yīng)數(shù)組索引中的值全部為1，這說(shuō)明這個(gè)元素可能存在前痘，如果對(duì)應(yīng)索引中的值凛捏，至少有一個(gè)為0，這說(shuō)明這個(gè)元素一定不存在
所以- 如果有一個(gè)哈希函數(shù)生成的索引位置不為1芹缔，就代表不存在（100%準(zhǔn)確）
- 如果每一個(gè)哈希函數(shù)生成的索引位置都為1坯癣，就代表存在，但存在一定的誤判率
所以最欠，根據(jù)布隆過(guò)濾器的原理示罗，可以知道
添加/查詢(xún)的時(shí)間復(fù)雜度為O(k)，其中k是哈希函數(shù)的個(gè)數(shù)
空間復(fù)雜度為O(m)芝硬，m是二進(jìn)制位的個(gè)數(shù)
布隆過(guò)濾器的誤判率
誤判率p一般來(lái)講蚜点，收到3個(gè)因素的影響，分別為
- 二進(jìn)制位的個(gè)數(shù)m
- 哈希函數(shù)的個(gè)數(shù)k
- 數(shù)據(jù)規(guī)模n
根據(jù)下圖中已知的公式拌阴，就能計(jì)算出當(dāng)前的誤判率p
由于在數(shù)據(jù)規(guī)模非常大時(shí)绍绘，n的值就非常大，所以可以忽略0,5的常系數(shù)，同時(shí)二進(jìn)制位的個(gè)數(shù)也會(huì)非常大陪拘，所以常數(shù)1也可以忽略厂镇，因此簡(jiǎn)化后的公式如下
所以實(shí)際開(kāi)發(fā)中，誤判率是結(jié)合業(yè)務(wù)來(lái)確定的左刽，因此誤判率可以認(rèn)為是一個(gè)已知的值捺信。并且數(shù)據(jù)規(guī)模也是已知的，所以就可以利用誤判率p和數(shù)據(jù)規(guī)模n得出二進(jìn)制位的個(gè)數(shù)m與哈希表的個(gè)數(shù)k
科學(xué)家總結(jié)出的公式如下：
計(jì)算二進(jìn)制位的個(gè)數(shù)
計(jì)算哈希表的個(gè)數(shù)
布隆過(guò)濾器的實(shí)現(xiàn)
結(jié)合前面介紹布隆過(guò)濾器的特性欠痴，可以知道迄靠，布隆過(guò)濾器有會(huì)提供2個(gè)API，分別是添加元素與查詢(xún)?cè)厥欠翊嬖?/p>
兩個(gè)API的實(shí)現(xiàn)如下
/*
* n為數(shù)據(jù)規(guī)模
* p為誤判率(0,1)
* */
public BloomFilter(int n,double p) {
if (n <= 0 || p <= 0 || p >= 1){
throw new IllegalArgumentException("wrong n or p");
}
double ln2 = Math.log(2);
//計(jì)算二進(jìn)制向量的長(zhǎng)度
bitSize = (int)(- (n * Math.log(p)) / (ln2 * ln2));
//計(jì)算哈希函數(shù)的個(gè)數(shù)
hashSize = (int)(bitSize * ln2 / n);
//bits數(shù)組的長(zhǎng)度
bits = new long[(int)((bitSize + Long.SIZE - 1)) / Long.SIZE];
}
/*
* 添加元素
* */
public void put(T value){
nullCheck(value);
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
//生成一個(gè)二進(jìn)制位的索引
int index = combinedHash % bitSize;
//設(shè)置index位置的二進(jìn)制位為1
set(index);
}
}
以上是兩個(gè)API的主要實(shí)現(xiàn)邏輯喇辽。具體實(shí)現(xiàn)可以查閱demo梨水。
完！
