建站
咨詢
售后
建站咨詢
新聞中心
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
一、認(rèn)識(shí)布隆過濾器
1、概念
布隆過濾器其實(shí)就是加快判定一個(gè)元素是否在集合中出現(xiàn)的方法。比如說在一個(gè)大字典中，要查找某個(gè)單詞是否存在，于是我們就可以使用布隆過濾器，快速高效省時(shí)省力。
這里有一個(gè)考察點(diǎn)，那就是布隆過濾器只能判定一個(gè)元素不在集合里面，不能判斷存在，什么意思呢!就是說一個(gè)蘋果不在籃子里，這個(gè)我可以通過布隆過濾器知道，但是一定在籃子里嘛?這個(gè)通過布隆過濾器我是不能判定的。
下面通過原理就能理解這個(gè)了。
2、原理
先舉一個(gè)例子，在我們身邊充斥著各種各樣的XX網(wǎng)站，為了不毒害我們祖國的花朵，于是國家網(wǎng)警就開始對(duì)這些網(wǎng)站進(jìn)行割除過濾，問題來了，這些網(wǎng)站的地址其實(shí)是不停的更換的，這些垃圾網(wǎng)站和正常網(wǎng)站加起來全世界據(jù)統(tǒng)計(jì)也有幾十億個(gè)。因此就會(huì)帶來如下的問題：
(1)網(wǎng)站數(shù)量太多，存儲(chǔ)起來比較麻煩。一個(gè)地址最起碼有32個(gè)字節(jié)，一億個(gè)地址就需要1.6G的內(nèi)存。
(2)一個(gè)一個(gè)比較，太費(fèi)時(shí)間了。
因此布隆過濾器被設(shè)計(jì)出來了，他是如何做到高效的呢?本質(zhì)上其實(shí)就是一個(gè)HASH映射器。他的底層其實(shí)是一個(gè)超大的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)?，F(xiàn)在我們按照之前的那個(gè)例子，我們存儲(chǔ)1億個(gè)垃圾網(wǎng)站地址。
(1)第一步：建立一個(gè)32億二進(jìn)制(比特)，也就是4億字節(jié)的向量。全部置0。
(2)第二步：網(wǎng)警用八個(gè)不同的隨機(jī)數(shù)產(chǎn)生器(F1,F2, …,F8) 產(chǎn)生八個(gè)信息指紋(f1, f2, …, f8)。
(3)第三步：用一個(gè)隨機(jī)數(shù)產(chǎn)生器 G 把這八個(gè)信息指紋映射到 1 到32億中的八個(gè)自然數(shù) g1, g2, …,g8。
(4)第四步：把這八個(gè)位置的二進(jìn)制全部設(shè)置為一。
OK，有一天網(wǎng)警查到了一個(gè)可疑的網(wǎng)站，想判斷一下是否是XX網(wǎng)站，于是就開始檢查了。通過同樣的方法將XX網(wǎng)站通過哈希映射到32億個(gè)比特位數(shù)組上的8個(gè)點(diǎn)。如果8個(gè)點(diǎn)的其中有一個(gè)點(diǎn)不為1，則可以判斷該元素一定不存在集合中。
注意：現(xiàn)在你可能會(huì)發(fā)現(xiàn)一個(gè)問題，如果兩個(gè)XX網(wǎng)站通過上面的步驟映射到了相同的8個(gè)點(diǎn)上，或者是有一部分點(diǎn)是重合的，這時(shí)候該怎么辦?于是就出現(xiàn)了誤報(bào)，也就是說A網(wǎng)站在12345678個(gè)點(diǎn)上全部置1，B網(wǎng)站通過同樣的方式在23456789上全部置1，這時(shí)候B網(wǎng)站來了是不能確定是否包含的。這個(gè)邏輯相信各位都理解。這個(gè)是最基礎(chǔ)的面試問題。
3、誤報(bào)率
這一小節(jié)是稍微高級(jí)一點(diǎn)點(diǎn)，某中廠問到了一次，于是這一次就添加了進(jìn)來。
通過上面的解釋相信都大概了解的差不多了，其實(shí)就是hash函數(shù)映射，由于有hash沖突產(chǎn)生了誤報(bào)率，誤報(bào)率也就是判斷失敗的情況。
既然是由于hash沖突，那我把布隆過濾器的二進(jìn)制向量調(diào)到很大，這樣不就解決了嘛，但是由于數(shù)據(jù)量比較大，因此現(xiàn)在就要考慮一下誤報(bào)率和存儲(chǔ)效率之間選擇一個(gè)折中值了。有一個(gè)計(jì)算公式如下：公式來源于github
假設(shè)位數(shù)組的長(zhǎng)度為m，哈希函數(shù)的個(gè)數(shù)為k。檢測(cè)某一元素是否在該集合中的誤報(bào)率是：
啥事布隆過濾器？主要干嘛用的？啥事布隆過濾器？主要干嘛用的？
如何使得誤報(bào)率最小，數(shù)學(xué)問題，求導(dǎo)就可以了。
4、使用場(chǎng)景
(1)google的guava包中有對(duì)Bloom Filter的實(shí)現(xiàn)
(2)通常使用布隆過濾器去解決redis中的緩存穿透，解決方案是redis中bitmap的實(shí)現(xiàn)，
(3)釣魚網(wǎng)站、垃圾郵件檢測(cè)
大體就這些，可能還有很多!!!
二、代碼實(shí)現(xiàn)布隆過濾器
上面只是給出了其原理，下面我們代碼實(shí)現(xiàn)一下。
public class MyBloomFilter {
// 2 "www.愚公要移山.com" ;
MyBloomFilter filter = new MyBloomFilter();
//加入之前判斷一下
System.out.println(filter.contains(value));
filter.add(value);
//加入之后判斷一下
System.out.println(filter.contains(value));
}
//構(gòu)造函數(shù)
public MyBloomFilter() {
for ( int i = 0 ; i for (SimpleHash f : func) {
bits.set(f.hash(value), true );
}
}
//判斷可疑網(wǎng)站是否存在
public boolean contains(String value) {
if (value == null ) {
return false ;
}
boolean ret = true ;
for (SimpleHash f : func) {
//核心就是通過“與”的操作
ret = ret && bits.get(f.hash(value));
}
return ret;
}
}
還有一個(gè)SimpleHash，我們看一下
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash( int cap, int seed) {
this .cap = cap;
this .seed = seed;
}
public int hash(String value) {
int result = 0 ;
int len = value.length();
for ( int i = 0 ; i return (cap - 1 ) & result;
}
}
這就是布隆過濾器的實(shí)現(xiàn)。
網(wǎng)頁題目：講解一下布隆過濾器
當(dāng)前地址：http://m.fisionsoft.com.cn/article/dpipoog.html
