1.定義
布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)瞒滴，特點(diǎn)是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”，由二進(jìn)制向量（或者說位數(shù)組）和一系列隨機(jī)映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結(jié)構(gòu)逸吵。
布隆過濾器是一種來檢索元素是否在給定大集合中的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)是高效且性能很好的缝裁，但缺點(diǎn)是具有一定的錯(cuò)誤識(shí)別率和刪除難度扫皱。并且，理論情況下，添加到集合中的元素越多韩脑，誤報(bào)的可能性就越大氢妈。
2.原理
- 插入元素時(shí)：
1.使用布隆過濾器中的哈希函數(shù)對(duì)元素值進(jìn)行計(jì)算，得到哈希值（有幾個(gè)哈希函數(shù)得到幾個(gè)哈希值）扰才。
2.根據(jù)不同哈希函數(shù)得到的哈希值允懂，在位數(shù)組中把對(duì)應(yīng)下標(biāo)的值置為 1。 - 判斷元素是否存在時(shí)：
1.對(duì)給定元素再次使用相同的哈希函數(shù)進(jìn)行哈希計(jì)算衩匣；
2.得到值之后判斷位數(shù)組中的每個(gè)元素是否都為 1蕾总，如果值都為 1，那么說明這個(gè)值在布隆過濾器中琅捏，如果存在一個(gè)值不為 1生百，說明該元素不在布隆過濾器中。
不同的字符串可能哈希出來的位置相同柄延，這種情況我們可以適當(dāng)增加位數(shù)組大小或者調(diào)整我們的哈希函數(shù)蚀浆。
綜上，我們可以得出：布隆過濾器說某個(gè)元素存在搜吧，小概率會(huì)誤判市俊。布隆過濾器說某個(gè)元素不在，那么這個(gè)元素一定不在滤奈。
3.使用場(chǎng)景
1.判斷給定數(shù)據(jù)是否存在：比如判斷一個(gè)數(shù)字是否存在于包含大量數(shù)字的數(shù)字集中（數(shù)字集很大摆昧，5億以上！）蜒程、 防止緩存穿透（判斷請(qǐng)求的數(shù)據(jù)是否有效避免直接繞過緩存請(qǐng)求數(shù)據(jù)庫(kù)）等等绅你、郵箱的垃圾郵件過濾、黑名單功能等等昭躺。
2.去重：比如爬給定網(wǎng)址的時(shí)候?qū)σ呀?jīng)爬取過的 URL 去重忌锯。
4.實(shí)現(xiàn)
import java.util.BitSet;
public class MyBloomFilter {
/**
* 位數(shù)組的大小
*/
private static final int DEFAULT_SIZE = 2 << 24;
/**
* 通過這個(gè)數(shù)組可以創(chuàng)建 6 個(gè)不同的哈希函數(shù)
*/
private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
/**
* 位數(shù)組。數(shù)組中的元素只能是 0 或者 1
*/
private BitSet bits = new BitSet(DEFAULT_SIZE);
/**
* 存放包含 hash 函數(shù)的類的數(shù)組
*/
private SimpleHash[] func = new SimpleHash[SEEDS.length];
/**
* 初始化多個(gè)包含 hash 函數(shù)的類的數(shù)組领炫，每個(gè)類中的 hash 函數(shù)都不一樣
*/
public MyBloomFilter() {
// 初始化多個(gè)不同的 Hash 函數(shù)
for (int i = 0; i < SEEDS.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
}
}
/**
* 添加元素到位數(shù)組
*/
public void add(Object value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
/**
* 判斷指定元素是否存在于位數(shù)組
*/
public boolean contains(Object value) {
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/**
* 靜態(tài)內(nèi)部類偶垮。用于 hash 操作！
*/
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
/**
* 計(jì)算 hash 值
*/
public int hash(Object value) {
int h;
return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
}
}
}
測(cè)試：
String value1 = "https://javaguide.cn/";
String value2 = "https://github.com/Snailclimb";
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
Output:
false
false
true
true
參考：JavaGuide
