建站
咨詢
售后
建站咨詢
新聞中心
前言
如果要判斷一個(gè)元素是否在集合中，一般的思路是保存集合中的所有元素，然后通過(guò)比較來(lái)確定。鏈表、樹(shù)、哈希表（也叫哈希表、哈希表）等數(shù)據(jù)結(jié)構(gòu)都是這種方式，存儲(chǔ)位置要么是磁盤(pán)，要么是內(nèi)存。很多時(shí)候，要么時(shí)間換空間，要么空間換時(shí)間。
10年的南部網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。網(wǎng)絡(luò)營(yíng)銷推廣的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整南部建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)建站從事“南部網(wǎng)站設(shè)計(jì)”,“南部網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。
在對(duì)響應(yīng)時(shí)間要求比較嚴(yán)格的情況下，如果我們有里面，那么隨著集合中元素?cái)?shù)量的增加，我們需要的存儲(chǔ)空間越來(lái)越大，檢索時(shí)間也越來(lái)越長(zhǎng)，導(dǎo)致內(nèi)存過(guò)多開(kāi)銷和時(shí)間效率變低。
這時(shí)候需要考慮的問(wèn)題是，在數(shù)據(jù)量比較大的情況下，既能滿足時(shí)間要求，又能滿足空間要求，所以我們需要一種時(shí)間和空間消耗都比較小的數(shù)據(jù)結(jié)構(gòu)和算法。布隆過(guò)濾器是一種解決方案。
什么是布隆過(guò)濾器？
Bloom Filter, 布隆過(guò)濾器由 Bloom于 1970 年提出。它實(shí)際上是一個(gè)長(zhǎng)二進(jìn)制向量和一系列隨機(jī)映射函數(shù), 布隆過(guò)濾器可用于檢索元素是否在集合中。其優(yōu)點(diǎn)是空間效率和查詢時(shí)間遠(yuǎn)超一般算法，缺點(diǎn)是存在一定的誤識(shí)別率和刪除難度。根據(jù)它的特性，應(yīng)用場(chǎng)景有如下：
- 爬蟲(chóng)過(guò)濾。
- 郵箱垃圾郵件過(guò)濾。
- 黑名單過(guò)濾。
- 大數(shù)據(jù)去重。
- 防止緩存穿透。
布隆過(guò)濾器原理
布隆過(guò)濾器的原理是當(dāng)一個(gè)元素加入到集合中時(shí)，通過(guò)K個(gè)哈希函數(shù)將該元素映射到一個(gè)位數(shù)組中的K個(gè)點(diǎn)，并將它們置為1。檢索時(shí)，我們只需要看這些點(diǎn)是否都為1，就可以（大概）知道它是否存在于集合中。如果這些點(diǎn)中的任何一個(gè)有0，則檢查的元素一定不存在。如果它們都是1，則被選中的元素很可能在那里。
Bloom Filter與單一哈希函數(shù)Bit-Map的區(qū)別在于，Bloom Filter使用k個(gè)哈希函數(shù)，每個(gè)字符串對(duì)應(yīng)k個(gè)bits，從而降低碰撞概率。
由于Bloom filter只存儲(chǔ)0和1而不存儲(chǔ)具體值，所以在一些機(jī)密場(chǎng)合具有先天優(yōu)勢(shì)。位圖的每一位都是一個(gè)位，所以通過(guò)位圖有10億個(gè)位置，位圖的大小為0.12G，插入和查詢的時(shí)間復(fù)雜度為O(k),k是哈希函數(shù)的個(gè)數(shù)。
布隆過(guò)濾器的問(wèn)題
布隆過(guò)濾器之所以能夠在時(shí)間和空間上取得比較高的效率，是因?yàn)樗鼱奚伺袛嗟臏?zhǔn)確性和刪除的便利性。
- 判斷錯(cuò)誤
有可能要找的元素不在容器中，但是散列后得到的k個(gè)位置都是1。如果布隆過(guò)濾器中存儲(chǔ)了黑名單，則可以通過(guò)創(chuàng)建白名單來(lái)存儲(chǔ)可能被誤判的元素。
對(duì)于這個(gè)問(wèn)題，可以通過(guò)增加位圖數(shù)組的大?。ㄎ粓D數(shù)組越大，占用的內(nèi)存越大）和減少哈希沖突來(lái)解決。但缺點(diǎn)是會(huì)增加占用的內(nèi)存空間。
另一種解決方案是增加散列函數(shù)的數(shù)量并減少散列沖突。如果同一個(gè)鍵值等于一個(gè)函數(shù)，經(jīng)過(guò)兩個(gè)或多個(gè)哈希函數(shù)得到相等結(jié)果的概率自然會(huì)降低。然而，這會(huì)導(dǎo)致計(jì)算效率的降低，因?yàn)闀r(shí)間復(fù)雜度退化為O(hash times)。
- 難以去除
放置在容器中的元素映射到位數(shù)組的 k 個(gè)位置中的 1。刪除的時(shí)候不能簡(jiǎn)單的直接設(shè)置為0，這樣可能會(huì)影響其他元素的判斷。你可以使用??Counting Bloom Filter??來(lái)解決這個(gè)問(wèn)題。
Java中如何使用布隆過(guò)濾器
google的guava就提供了這樣的API.
com.google.guava
guava
22.0
編寫(xiě)測(cè)試代碼
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class GuavaBloomFilter {
public static void main(String[] args) {
int total = 1000000;
// default false positive ratefpp0.03
// fpp:There will always be a false positive rate in a Bloom filter
// Because hash collisions are impossible to avoid 100%.
// Bloom filter calls this misjudgment rate false positive probability，abbreviated as fpp
BloomFilterbf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
// Initialize the total bar data into the filter
for (int i = 0; i < total; i++) {
bf.put("" + i);
}
// Determine whether the value exists in the filter
int count = 0;
for (int i = 0; i < total + 10000; i++) {
if (bf.mightContain("" + i)) {
count++;
}
}
System.out.println("Matched quantity " + count);
// Specified misjudgment rate: 1/10,000 to improve matching accuracy
BloomFilterbfWithFpp = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);
for (int i = 0; i < total; i++) {
bfWithFpp.put("" + i);
}
int countFpp = 0;
for (int i = 0; i < total + 10000; i++) {
if (bfWithFpp.mightContain("" + i)) {
countFpp++;
}
}
//The smaller the value of the false positive rate fpp
// the higher the matching accuracy.
// When the value of the false positive rate fpp is reduced
// the storage space required is also larger
// Therefore, in actual use,
// a trade-off needs to be made between the false positive rate and the storage space.
System.out.println("The specified false positive rate has matched the number " + countFpp);// (1000001 - 1000000)/(1000000 + 10000) * 100 ≈ 0.0001
}
}
網(wǎng)站欄目：什么是布隆過(guò)濾器？你學(xué)會(huì)了嗎？
文章來(lái)源：http://fisionsoft.com.cn/article/ccegods.html
