建站
咨詢
售后
建站咨詢
新聞中心
布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點(diǎn)是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”。
創(chuàng)新互聯(lián)建站網(wǎng)站建設(shè)公司一直秉承“誠信做人，踏實(shí)做事”的原則，不欺瞞客戶，是我們最起碼的底線！ 以服務(wù)為基礎(chǔ)，以質(zhì)量求生存，以技術(shù)求發(fā)展，成交一個(gè)客戶多一個(gè)朋友！專注中小微企業(yè)官網(wǎng)定制，做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)，塑造企業(yè)網(wǎng)絡(luò)形象打造互聯(lián)網(wǎng)企業(yè)效應(yīng)。
在正式講解布隆過濾器之前，先讓我們看看這個(gè)業(yè)務(wù)場景：
Redis 是軟件架構(gòu)中常用的組件，最常見的用法是將熱點(diǎn)數(shù)據(jù)緩存到 Redis 中，以減少數(shù)據(jù)庫的壓力;查詢過程中最常見的用法是：查詢 Redis，如果能查詢到則直接返回，如果 Redis 中不存在則繼續(xù)查詢數(shù)據(jù)庫。
這種方式可以減少數(shù)據(jù)庫的訪問次數(shù)，但是“當(dāng)緩存中沒有，就查詢數(shù)據(jù)庫”，在高并發(fā)的環(huán)境中依然會(huì)有風(fēng)險(xiǎn)，比如 90% 的請(qǐng)求數(shù)據(jù)都不在緩存中，那么這些請(qǐng)求就都會(huì)落到數(shù)據(jù)庫上，這就是緩存穿透。
那么有沒有什么辦法解決這個(gè)問題呢?這就可以使用【布隆過濾器】了，它可以確定“某項(xiàng)數(shù)據(jù)肯定不存在”。
01.布隆過濾器的概念
布隆過濾器是一個(gè)叫“布隆”的人提出的，它本身是一個(gè)很長的二進(jìn)制向量(想象成數(shù)組)和一系列隨機(jī)映射函數(shù)(想象成多個(gè) Hash 函數(shù))，二進(jìn)制向量中存放的不是0，就是1(在學(xué)習(xí)布隆過濾器之前，可以先了解 BitMap 算法，便于理解)。
比如要根據(jù)客戶手機(jī)號(hào)做為條件查詢客戶信息，通常會(huì)把手機(jī)號(hào)碼設(shè)置成緩存中的 Key，讓我們?cè)O(shè)置一個(gè)長度為 16 的布隆過濾器。
布隆過濾器初始化都是 0;
對(duì) 13800000000 分別進(jìn)行 hash1()、hash2()、hash3() 運(yùn)算，得到三個(gè)結(jié)果 5、9、12，把對(duì)應(yīng)位置設(shè)置成 1;
對(duì) 18900000000 分別進(jìn)行 hash1()、hash2()、hash3() 運(yùn)算，得到三個(gè)結(jié)果 2、8、12，把對(duì)應(yīng)位置設(shè)置成 1，現(xiàn)在 2、5、8、9、12 都是 1，其余元素都是 0;
如果我們想要驗(yàn)證某個(gè)電話號(hào)碼是否存在，需要怎么做呢?
對(duì) 13700000000 分別進(jìn)行 hash1()、hash2()、hash3() 運(yùn)算，得到三個(gè)結(jié)果 1、9、13，然后去判斷第 1、9、13 位上的值是 0 還是 1，如果不全是 1 的話，就說明 13700000000 不在這個(gè)布隆過濾器上;這就確定了“某項(xiàng)數(shù)據(jù)肯定不存在”。
當(dāng)然我們也可以看出來布隆過濾器有個(gè)問題，那就是不能保證數(shù)據(jù)肯定存在，比如對(duì) 18000000000 分別進(jìn)行 hash1()、hash2()、hash3() 運(yùn)算，得到的結(jié)果是 5、8、9，恰好這三位都是 1，但實(shí)際上這條數(shù)據(jù)并不存在，所以布隆過濾器有一定的誤判率;
而且因?yàn)槎鄠€(gè)數(shù)據(jù)經(jīng)過運(yùn)算后可能會(huì)映射到同一個(gè)位置(138 和 189 的運(yùn)算結(jié)果都有 12)，所以布隆過濾器很難做到刪除，除非要為每一位增加一個(gè)計(jì)數(shù)器，刪除的時(shí)候需要給計(jì)數(shù)器減 1，直到計(jì)數(shù)器為 0 時(shí)，才將布隆過濾器對(duì)應(yīng)位置修改成 0。
02.特點(diǎn)總結(jié)
可以確定一個(gè)元素肯定不存在，但是不能確定一個(gè)元素肯定存在;
二進(jìn)制向量越長，映射函數(shù)越多，誤判率越低;如果提前可以確定誤判率，也可以反推出來布隆過濾器的長度;
可以添加元素，但是不能刪除元素(除非增加計(jì)數(shù)器);
在存儲(chǔ)空間和插入查詢的時(shí)間復(fù)雜度都有巨大優(yōu)勢。
回到本文開頭的那個(gè)業(yè)務(wù)場景，為了防止緩存穿透，可以使用布隆過濾器過濾掉肯定不存在的數(shù)據(jù)，誤判的請(qǐng)求雖然還是會(huì)放到到數(shù)據(jù)庫，但已經(jīng)極大地減少了穿透的數(shù)量。
03.手寫一個(gè)布隆過濾器
Code 不是目的，Coding 的過程是為了加深理解。
首先我們需要定義一個(gè) bitmap，在 JDK 中，已經(jīng)有對(duì)應(yīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類 java.util.BitSet：
//設(shè)置一個(gè)布隆過濾器
private int DEFAULT_SIZE = 1 我們還需要一組映射函數(shù)，這里可以使用加法 hash 函數(shù)，設(shè)置 6 個(gè)質(zhì)數(shù)，對(duì)應(yīng) 6 個(gè)不同的 hash 函數(shù)：
//定義一個(gè)質(zhì)數(shù)數(shù)組，長度為6，可以生成6個(gè)hash函數(shù)，用于隨機(jī)映射
private int[] seeds = {3, 7, 13, 31, 37, 61};
private HashFunction[] functions = new HashFunction[seeds.length];
在構(gòu)造函數(shù)中進(jìn)行初始化，設(shè)置 BitSet 的長度，生成映射函數(shù)：
/**
* 初始化
*/
public BloomFilter() {
bitset = new BitSet(DEFAULT_SIZE);
for (int i = 0; i functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
}
}
增加元素的時(shí)候，對(duì)入?yún)⑦M(jìn)行 6 次 hash 運(yùn)算，并將結(jié)果對(duì)應(yīng)的位置修改成 1(BitSet 對(duì)應(yīng)的位置修改成 true)：
/**
* 添加一個(gè)元素，得到hash運(yùn)算后的結(jié)果，將對(duì)應(yīng)的位置修改成1（true）
* @param value
*/
public void add(String value) {
if (value != null) {
for (HashFunction f : functions) {
bitset.set(f.hash(value), true);
}
}
}
判斷元素是否在布隆管理器中，需要對(duì)入?yún)⑦M(jìn)行 6 次 hash 運(yùn)算，再查看結(jié)果對(duì)應(yīng)的位置上是 0 還是 1(true or false)，如果其中一位是 0，表示數(shù)據(jù)肯定不存在，如果都是 1，表示數(shù)據(jù)(大概率)可能存在。
/**
* 判斷元素是否在布隆過濾器中
* @param value
* @return
*/
public boolean contains(String value) {
if (value == null) {
return false;
}
for (HashFunction f : functions) {
if(!bitset.get(f.hash(value))){
//一個(gè)位置上不為1（true），就證明不存在，直接返回false
return false;
}
}
return true;
}
04.Guava 中的 BloomFilter
已經(jīng)有很多開源框架幫我們實(shí)現(xiàn)了布隆管理器，比如 Google 出品的 Guava 工具庫，其中就有開箱即用的布隆過濾器;
public class BloomFilterTest {
public static void main(String[] args){
int size = 1000000;
//布隆過濾器
BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.001);
for (int i = 0; i for (int i = size + 1; i if (bloomFilter.mightContain(i)) {
list.add(i);
}
}
System.out.println("誤判數(shù)量：" + list.size());
}
}
文章名稱：簡單講解一下布隆過濾器
本文來源：http://www.dlmjj.cn/article/ccojggp.html
