布隆過(guò)濾器使用場(chǎng)景
之前在《數(shù)學(xué)之美》里面看到過(guò)布隆過(guò)濾器的介紹阳似。那么什么場(chǎng)景下面需要使用布隆過(guò)濾器呢?
看下下面幾個(gè)問(wèn)題
- 字處理軟件中咸这,需要檢查一個(gè)英語(yǔ)單詞是否拼寫(xiě)正確
- 在 FBI痒蓬,一個(gè)嫌疑人的名字是否已經(jīng)在嫌疑名單上
- 在網(wǎng)絡(luò)爬蟲(chóng)里,一個(gè)網(wǎng)址是否被訪問(wèn)過(guò)
- yahoo, gmail等郵箱垃圾郵件過(guò)濾功能
以上這些場(chǎng)景有個(gè)共同的問(wèn)題:如何查看一個(gè)東西是否在有大量數(shù)據(jù)的池子里面贪惹。
通常的做法有如下幾種思路:
- 數(shù)組
- 鏈表
- 樹(shù)苏章、平衡二叉樹(shù)、Trie
- Map (紅黑樹(shù))
- 哈希表
上面這幾種數(shù)據(jù)結(jié)構(gòu)配合一些搜索算法是可以解決數(shù)據(jù)量不大的問(wèn)題的奏瞬,如果當(dāng)集合里面的數(shù)據(jù)量非常大的時(shí)候枫绅,就會(huì)有問(wèn)題。比如:
有500萬(wàn)條記錄甚至1億條記錄硼端?這個(gè)時(shí)候常規(guī)的數(shù)據(jù)結(jié)構(gòu)的問(wèn)題就凸顯出來(lái)了并淋。數(shù)組、鏈表显蝌、樹(shù)等數(shù)據(jù)結(jié)構(gòu)會(huì)存儲(chǔ)元素的內(nèi)容预伺,一旦數(shù)據(jù)量過(guò)大,消耗的內(nèi)存也會(huì)呈現(xiàn)線性增長(zhǎng)曼尊,最終達(dá)到瓶頸酬诀。哈希表查詢效率可以達(dá)到O(1)。但是哈希表需要消耗的內(nèi)存依然很高骆撇。使用哈希表存儲(chǔ)一億 個(gè)垃圾 email 地址的消耗瞒御?哈希表的做法:首先,哈希函數(shù)將一個(gè)email地址映射成8字節(jié)信息指紋神郊;考慮到哈希表存儲(chǔ)效率通常小于50%(哈希沖突)肴裙;因此消耗的內(nèi)存:8 * 2 * 1億 字節(jié) = 1.6G 內(nèi)存,普通計(jì)算機(jī)是無(wú)法提供如此大的內(nèi)存涌乳。這個(gè)時(shí)候蜻懦,布隆過(guò)濾器(Bloom Filter)就應(yīng)運(yùn)而生。
在繼續(xù)介紹布隆過(guò)濾器的原理時(shí)夕晓,先講解下關(guān)于哈希函數(shù)的預(yù)備知識(shí)宛乃。
哈希函數(shù)
哈希函數(shù)的概念是:將任意大小的數(shù)據(jù)轉(zhuǎn)換成特定大小的數(shù)據(jù)的函數(shù),轉(zhuǎn)換后的數(shù)據(jù)稱為哈希值或哈希編碼。下面是一幅示意圖:
可以明顯的看到征炼,原始數(shù)據(jù)經(jīng)過(guò)哈希函數(shù)的映射后稱為了一個(gè)個(gè)的哈希編碼析既,數(shù)據(jù)得到壓縮。哈希函數(shù)是實(shí)現(xiàn)哈希表和布隆過(guò)濾器的基礎(chǔ)谆奥。
布隆過(guò)濾器介紹
- 巴頓.布隆于一九七零年提出
- 一個(gè)很長(zhǎng)的二進(jìn)制向量 (位數(shù)組)
- 一系列隨機(jī)函數(shù) (哈希)
- 空間效率和查詢效率高
- 不會(huì)漏判眼坏,但是有一定的誤判率(哈希表是精確匹配)
布隆過(guò)濾器原理
布隆過(guò)濾器(Bloom Filter)的核心實(shí)現(xiàn)是一個(gè)超大的位數(shù)組和幾個(gè)哈希函數(shù)。假設(shè)位數(shù)組的長(zhǎng)度為m酸些,哈希函數(shù)的個(gè)數(shù)為k
以上圖為例宰译,具體的操作流程:假設(shè)集合里面有3個(gè)元素{x, y, z},哈希函數(shù)的個(gè)數(shù)為3擂仍。首先將位數(shù)組進(jìn)行初始化囤屹,將里面每個(gè)位都設(shè)置位0。對(duì)于集合里面的每一個(gè)元素逢渔,將元素依次通過(guò)3個(gè)哈希函數(shù)進(jìn)行映射肋坚,每次映射都會(huì)產(chǎn)生一個(gè)哈希值,這個(gè)值對(duì)應(yīng)位數(shù)組上面的一個(gè)點(diǎn)肃廓,然后將位數(shù)組對(duì)應(yīng)的位置標(biāo)記為1智厌。查詢W元素是否存在集合中的時(shí)候,同樣的方法將W通過(guò)哈希映射到位數(shù)組上的3個(gè)點(diǎn)盲赊。如果3個(gè)點(diǎn)的其中有一個(gè)點(diǎn)不為1铣鹏,則可以判斷該元素一定不存在集合中。反之哀蘑,如果3個(gè)點(diǎn)都為1诚卸,則該元素可能存在集合中。注意:此處不能判斷該元素是否一定存在集合中绘迁,可能存在一定的誤判率合溺。可以從圖中可以看到:假設(shè)某個(gè)元素通過(guò)映射對(duì)應(yīng)下標(biāo)為4缀台,5棠赛,6這3個(gè)點(diǎn)。雖然這3個(gè)點(diǎn)都為1膛腐,但是很明顯這3個(gè)點(diǎn)是不同元素經(jīng)過(guò)哈希得到的位置睛约,因此這種情況說(shuō)明元素雖然不在集合中,也可能對(duì)應(yīng)的都是1哲身,這是誤判率存在的原因辩涝。
添加元素
- 將要添加的元素給k個(gè)哈希函數(shù)
- 得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置
- 將這k個(gè)位置設(shè)為1
查詢?cè)?/h1>
- 將要查詢的元素給k個(gè)哈希函數(shù)
- 得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置
- 如果k個(gè)位置有一個(gè)為0,則肯定不在集合中
- 如果k個(gè)位置全部為1勘天,則可能在集合中
github代碼
簡(jiǎn)易實(shí)現(xiàn)
import java.util.BitSet;
/**
* Created by haicheng.lhc on 18/05/2017.
*
* @author haicheng.lhc
* @date 2017/05/18
*/
public class SimpleBloomFilter {
private static final int DEFAULT_SIZE = 2 << 24;
private static final int[] seeds = new int[] {7, 11, 13, 31, 37, 61,};
private BitSet bits = new BitSet(DEFAULT_SIZE);
private SimpleHash[] func = new SimpleHash[seeds.length];
public static void main(String[] args) {
String value = " stone2083@yahoo.cn ";
SimpleBloomFilter filter = new SimpleBloomFilter();
System.out.println(filter.contains(value));
filter.add(value);
System.out.println(filter.contains(value));
}
public SimpleBloomFilter() {
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
public void add(String value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
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;
}
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 < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
}
import java.util.BitSet;
/**
* Created by haicheng.lhc on 18/05/2017.
*
* @author haicheng.lhc
* @date 2017/05/18
*/
public class SimpleBloomFilter {
private static final int DEFAULT_SIZE = 2 << 24;
private static final int[] seeds = new int[] {7, 11, 13, 31, 37, 61,};
private BitSet bits = new BitSet(DEFAULT_SIZE);
private SimpleHash[] func = new SimpleHash[seeds.length];
public static void main(String[] args) {
String value = " stone2083@yahoo.cn ";
SimpleBloomFilter filter = new SimpleBloomFilter();
System.out.println(filter.contains(value));
filter.add(value);
System.out.println(filter.contains(value));
}
public SimpleBloomFilter() {
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
public void add(String value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
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;
}
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 < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
}