Java中的布隆過(guò)濾器，你知道嗎？
原理
布隆過(guò)濾器（Bloom Filter）是1970年由伯頓·霍華德·布?。˙urton Howard Bloom）提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。
布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢(xún)時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將集合中所有元素保存起來(lái)，然后通過(guò)比較確定。鏈表、樹(shù)、散列表（又叫哈希表，Hash Table）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來(lái)越大。同時(shí)檢索速度也越來(lái)越慢，上述三種結(jié)構(gòu)的檢索時(shí)間復(fù)雜度分別為O(n)、O(logn)、O(1)。
布隆過(guò)濾器的原理是，當(dāng)一個(gè)元素被加入集合時(shí)，通過(guò)K個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的K個(gè)點(diǎn)，把它們置為1。
圖片
檢索時(shí)，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒(méi)有它了：如果這些點(diǎn)有任何一個(gè)0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。
圖片
接下來(lái)，我們看下在Java中怎么使用。
單機(jī)版：Guava
首先引入依賴(lài)：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>33.2.1-jre</version>
</dependency>然后使用Guava中的BloomFilter類(lèi)開(kāi)始實(shí)現(xiàn)：
@Test
public void testBloomFilter() {
final List<String> itemsToInsert = Arrays.asList("apple", "banana", "cherry", "elderberry");
// 創(chuàng)建布隆過(guò)濾器
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100, 0.01);
// 當(dāng)前元素?cái)?shù)量為0
Assertions.assertEquals(0, bloomFilter.approximateElementCount());
// 向布隆過(guò)濾器中插入數(shù)據(jù)
for (String item : itemsToInsert) {
bloomFilter.put(item);
}
// 當(dāng)前元素?cái)?shù)量為4
Assertions.assertEquals(4, bloomFilter.approximateElementCount());
// 測(cè)試已插入的數(shù)據(jù)
for (String item : itemsToInsert) {
Assertions.assertTrue(bloomFilter.mightContain(item), "Item should be in the Bloom Filter: " + item);
}
// 測(cè)試未插入的數(shù)據(jù)
final List<String> itemsNotInserted = Arrays.asList("grape", "orange", "peach", "quince", "raspberry");
for (String item : itemsNotInserted) {
Assertions.assertFalse(bloomFilter.mightContain(item), "Item should not be in the Bloom Filter: " + item);
}
}Guava實(shí)現(xiàn)的是單機(jī)版，雖然提供了文件寫(xiě)出的功能，可以將文件分發(fā)到分布式系統(tǒng)中，但是這種方式只能是補(bǔ)充。推薦只在單機(jī)場(chǎng)景中使用Guava的布隆過(guò)濾器。
如果想要在分布式服務(wù)中使用，可以選擇Redission。
分布式版：Redission
引入依賴(lài)：
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.11.5</version>
</dependency>使用Docker在本地啟一個(gè)Redis服務(wù)，用來(lái)驗(yàn)證：
docker run -d -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest然后編碼測(cè)試：
@Test
public void testBloomFilter() {
// 使用Docker本地啟動(dòng)一個(gè)Redis服務(wù)用來(lái)測(cè)試：
// docker run -d -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
// 生成key是 myBloomFilter 的存儲(chǔ)
// 會(huì)生成兩個(gè)key，"myBloomFilter"、"{myBloomFilter}:config"
// "myBloomFilter"是string類(lèi)型，布隆過(guò)濾器的主存
// "{myBloomFilter}:config"是hash結(jié)構(gòu)，存儲(chǔ)元信息，比如大小size、期望容量expectedInsertions、誤報(bào)率falseProbability、使用的哈希函數(shù)數(shù)量hashIterations等。
RBloomFilter<String> bloomFilter = Redisson.create(config)
.getBloomFilter("myBloomFilter");
// 初始化布隆過(guò)濾器，定義期望容量和誤報(bào)率
bloomFilter.tryInit(1000000, 0.01);
// 準(zhǔn)備一些測(cè)試數(shù)據(jù)
final List<String> itemsToInsert = Arrays.asList("apple", "banana", "cherry", "elderberry");
// 向布隆過(guò)濾器中插入數(shù)據(jù)
for (String item : itemsToInsert) {
bloomFilter.add(item);
}
// 測(cè)試已插入的數(shù)據(jù)
for (String item : itemsToInsert) {
Assertions.assertTrue(bloomFilter.contains(item), "Item should be in the Bloom Filter: " + item);
}
// 測(cè)試未插入的數(shù)據(jù)
final List<String> itemsNotInserted = Arrays.asList("grape", "orange", "peach", "quince", "raspberry");
for (String item : itemsNotInserted) {
Assertions.assertFalse(bloomFilter.contains(item), "Item should not be in the Bloom Filter: " + item);
}
}使用Redission的RBloomFilter，會(huì)根據(jù)布隆過(guò)濾器名字在Redis中生成兩個(gè)key，比如上面代碼的名字是“myBloomFilter”，生成的配置為：
- "myBloomFilter"是string類(lèi)型，布隆過(guò)濾器的主存，用來(lái)存儲(chǔ)二進(jìn)制數(shù)組；
- "{myBloomFilter}:config"是hash結(jié)構(gòu)，存儲(chǔ)元信息，比如大小size、期望容量expectedInsertions、誤報(bào)率falseProbability、使用的哈希函數(shù)數(shù)量hashIterations等。
