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