1. 概念
Bloom Filter可以理解為是一個m位的數(shù)組翩剪，它有k個相互獨立的哈希函數(shù)腕柜。每當新來一個元素時膀篮，會使用這些哈希函數(shù)分別計算毯焕，將對應(yīng)位置置為1衍腥。查詢時也要進行k次哈希運算，如果對應(yīng)的k個位置都為1纳猫，則表明元素可能存在婆咸。
Bloom Filter示意圖：
假如當前的過濾器中已經(jīng)記錄了1、10芜辕，此時判斷3是否存在尚骄，匹配之后發(fā)現(xiàn)并不存在
（圖中的方格就代表著數(shù)組，每個數(shù)字指向二位數(shù)組的線就代表一個哈希元素侵续。）
注：布隆過濾器只能判斷某個值一定不存在倔丈，無法判斷某個值一定存在憨闰。
2. 具體使用
2.1 google.guava
Google在guava包中提供了一個布隆過濾器的實現(xiàn)——com.google.common.hash.BloomFilter
put(T object) //往布隆過濾器中存入object
mightContain(T object) //判斷object是否存在
直接貼代碼，首先是pom
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.1.1-jre</version>
</dependency>
首先在配置類中創(chuàng)建BloomFilter的Bean需五，方便注入引用
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import java.nio.charset.Charset;
@Configuration
public class GoogleBloomFilter {
@Bean
public BloomFilter<String> initBloomFilterHelper() {
return BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.00001);
}
}
模擬插入操作鹉动，如果存在則不插入。
@RestController
@RequestMapping("/bloom")
@AllArgsConstructor
public class RedisController {
private final BloomFilter bloomFilter;
@GetMapping("/string/add")
public String redisString(String value){
boolean isExist = bloomFilter.mightContain(value);
System.out.println(value+ "是否存在：" + isExist);
if (!isExist) {
System.out.println("插入：" + value);
bloomFilter.put(value);
}
return String.valueOf(isExist);
}
}
測試用例：
13333333333
13333333334
13333333335
13333333336
13333333337
13333333335
13333333337
結(jié)果：
13333333333是否存在：false
插入：13333333333
13333333334是否存在：false
插入：13333333334
13333333335是否存在：false
插入：13333333335
13333333336是否存在：false
插入：13333333336
13333333337是否存在：false
插入：13333333337
13333333335是否存在：true
13333333337是否存在：true
2.2 google.guava的BloomFilter源碼解析
首先看一下BloomFilter的成員變量
/** BloomFilter的位集宏邮，也就是上文所說的數(shù)組 */
private final LockFreeBitArray bits;
/** 表示哈希函數(shù)的個數(shù) */
private final int numHashFunctions;
/** 把任意類型的數(shù)據(jù)轉(zhuǎn)換為Java基本數(shù)據(jù)類型泽示，最終轉(zhuǎn)化為byte數(shù)組 */
private final Funnel<? super T> funnel;
/** 內(nèi)部接口，將元素T映射到numHashFunctions位索引的策略 */
private final Strategy strategy;
然后看一下4個構(gòu)造方法
public static <T> BloomFilter<T> create(
Funnel<? super T> funnel, int expectedInsertions, double fpp) {
return create(funnel, (long) expectedInsertions, fpp);
}
public static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp) {
return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
return create(funnel, (long) expectedInsertions);
}
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}
四個構(gòu)造方法沒太大的區(qū)別蜀铲，最后都會指向同一個create方法
這個方法中接收了4個參數(shù)：funnel（輸入的數(shù)據(jù)）边琉，expectedInsertions（預(yù)計插入的元素總數(shù)），fpp（期望誤判率）记劝，strategy（實現(xiàn)Strategy的實例，參考上面的公共構(gòu)造方法族扰，默認傳遞的是BloomFilterStrategies.MURMUR128_MITZ_64）
@VisibleForTesting
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
//各種參數(shù)校驗
checkNotNull(funnel);
checkArgument(
expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
checkNotNull(strategy);
if (expectedInsertions == 0) {
expectedInsertions = 1;
}
/*
* TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size
* is proportional to -log(p), but there is not much of a point after all, e.g.
* optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
*/
//計算數(shù)組長度
long numBits = optimalNumOfBits(expectedInsertions, fpp);
//計算出每個元素需要哈希方法的個數(shù)
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
//創(chuàng)建BloomFilter對象
return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
}
}
最后再看一下BloomFilter這個構(gòu)造方法厌丑，很簡單，檢查完了之后給4個成員變量賦值
/** Creates a BloomFilter. */
private BloomFilter(
LockFreeBitArray bits, int numHashFunctions, Funnel<? super T> funnel, Strategy strategy) {
checkArgument(numHashFunctions > 0, "numHashFunctions (%s) must be > 0", numHashFunctions);
checkArgument(
numHashFunctions <= 255, "numHashFunctions (%s) must be <= 255", numHashFunctions);
this.bits = checkNotNull(bits);
this.numHashFunctions = numHashFunctions;
this.funnel = checkNotNull(funnel);
this.strategy = checkNotNull(strategy);
}
再看一下mightContain方法和put方法
public boolean mightContain(T object) {
return strategy.mightContain(object, funnel, numHashFunctions, bits);
}
@CanIgnoreReturnValue
public boolean put(T object) {
return strategy.put(object, funnel, numHashFunctions, bits);
}
都是調(diào)用的成員變量strategy的方法渔呵，我們知道構(gòu)造函數(shù)的strategy的參數(shù)都是BloomFilterStrategies.MURMUR128_MITZ_64這個枚舉值怒竿，貼一下代碼
MURMUR128_MITZ_64() {
@Override
public <T> boolean put(
T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
long bitSize = bits.bitSize();
byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
boolean bitsChanged = false;
long combinedHash = hash1;
for (int i = 0; i < numHashFunctions; i++) {
// Make the combined hash positive and indexable
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
combinedHash += hash2;
}
return bitsChanged;
}
@Override
public <T> boolean mightContain(
T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
long bitSize = bits.bitSize();
byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
long combinedHash = hash1;
for (int i = 0; i < numHashFunctions; i++) {
// Make the combined hash positive and indexable
if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
return false;
}
combinedHash += hash2;
}
return true;
}
抽象來看，put是寫扩氢，mightContain是讀耕驰，兩個方法的代碼有一點相似，都是先利用murmur3 hash對輸入的funnel計算得到128位的字節(jié)數(shù)組录豺，然后高低分別取8個字節(jié)（64位）創(chuàng)建2個long型整數(shù)hash1朦肘，hash2作為哈希值。循環(huán)體內(nèi)采用了2個函數(shù)模擬其他函數(shù)的思想双饥，即上文提到的gi(x) = h1(x) + ih2(x) 媒抠，這相當于每次累加hash2，然后通過基于bitSize取模的方式在bit數(shù)組中索引咏花。
這里之所以要和Long.MAX_VALUE進行按位與的操作趴生，是因為在除數(shù)和被除數(shù)符號不一致的情況下計算所得的結(jié)果是有差別的，在程序語言里昏翰，“%”準確來說是取余運算（C苍匆，C++和Java均如此，python是取模）棚菊，如-5%3=-2浸踩，而取模的數(shù)學(xué)定義是x mod y=x-y[x/y]（向下取整），所以-5 mod 3= -5-3*(-2)=1窍株，因此當哈希值為負數(shù)的時候民轴，其取余的結(jié)果為負（bitSize始終為正數(shù)）攻柠，這樣就不方便在bit數(shù)組中取值，因此通過Long.MAX_VALUE(二進制為0111…1111)后裸，直接將開頭的符號位去掉瑰钮，從而轉(zhuǎn)變?yōu)檎龜?shù)。當然也可以取絕對值微驶，在另一個MURMUR128_MITZ_32的實現(xiàn)中就是這么做的浪谴。
在put方法中，先是將索引位置上的二進制置為1因苹，然后用bitsChanged記錄插入結(jié)果苟耻，如果返回true表明沒有重復(fù)插入成功，而mightContain方法則是將索引位置上的數(shù)值取出扶檐，并判斷是否為0凶杖，只要其中出現(xiàn)一個0，那么立即判斷為不存在款筑。
這種使用方式屬于單機版的布隆過濾器的使用智蝠，在分布式場景下并不試用，所以需要redis來做一個分布式場景下的布隆過濾器
總結(jié)：
- BloomFilter類就是利用公式完成對參數(shù)的估算奈梳，創(chuàng)建了一個本地的BitArray數(shù)組（一個Long類型的數(shù)組杈湾，長度m）和需要哈希方法的次數(shù)k。
- 之后利用MURMUR128_MITZ_64這個枚舉值中的方法來進行運算攘须，在put方法中漆撞，利用計算出來的k個數(shù)值。在BitArray中于宙，以這k個數(shù)值為下標浮驳，將原有為0的值修改為1。
- mightContain方法中限煞，跟put方法同理抹恳，計算出k個數(shù)值，在BitArray中判斷這些數(shù)值為下標的值是否為0署驻，只要出現(xiàn)一個0則返回false奋献。
- 僅適合一個節(jié)點的使用，因為分布式中每個節(jié)點的BloomFilter的bean都是獨立的旺上。
2.3 利用Redis Bitmaps進行重構(gòu)
大致思路：創(chuàng)建一個新的BloomFilter瓶蚂，4個成員變量中，將Strategy這個變量改為使用Redis BitMap宣吱，其余的3個成員變量及計算方式保留窃这。將MURMUR128_MITZ_64中的Hashing.murmur3_128()方法拿出來，得到計算出來的k個下標征候，之后循環(huán)這些下標將BitMap中的這些值修改為1杭攻。
了解下Redis Bitmaps的結(jié)構(gòu)祟敛，推薦一篇不錯的博客：https://www.cnblogs.com/54chensongxia/p/13794391.html
下面貼代碼。
首先創(chuàng)建一個BloomFilter類
import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;
public class BloomFilterHelper<T> {
private int numHashFunctions;
private int bitSize;
private Funnel<T> funnel;
public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
Preconditions.checkArgument(funnel != null, "funnel不能為空");
this.funnel = funnel;
// 計算bit數(shù)組長度
bitSize = optimalNumOfBits(expectedInsertions, fpp);
// 計算hash方法執(zhí)行次數(shù)
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public int[] murmurHashOffset(T value) {
int[] offset = new int[numHashFunctions];
long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int nextHash = hash1 + i * hash2;
if (nextHash < 0) {
nextHash = ~nextHash;
}
offset[i - 1] = nextHash % bitSize;
}
return offset;
}
/**
* 計算bit數(shù)組長度
* @param n 預(yù)計插入的元素總數(shù)
* @param p 期望誤判率
* @return
*/
private int optimalNumOfBits(long n, double p) {
if (p == 0) {
// 設(shè)定最小期望長度
p = Double.MIN_VALUE;
}
int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
return sizeOfBitArray;
}
/**
* 計算hash方法執(zhí)行次數(shù)
* @param n 預(yù)計插入的元素總數(shù)
* @param m bit數(shù)組長度
* @return
*/
private int optimalNumOfHashFunctions(long n, long m) {
int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
return countOfHash;
}
}
接下來就是初始化一個上面自己實現(xiàn)的布隆過濾器類的bean
import com.google.common.base.Charsets;
import com.google.common.hash.Funnel;
import com.yyhd.redisdemo.filter.BloomFilterHelper;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
@Configuration
public class GoogleBloomFilter {
@Bean
public BloomFilterHelper<String> initBloomFilterHelper() {
BloomFilterHelper<String> bloomFilter = new BloomFilterHelper((Funnel<String>) (from, into) -> {
into.putString(from, Charsets.UTF_8);
}, 1000000, 0.0000001);
return bloomFilter;
}
}
之后創(chuàng)建BloomFilterUtil（主要操作的類）兆解，利用BloomFilterHelper的murmurHashOffset計算出哈希方法的數(shù)組馆铁，循環(huán)數(shù)組以每個值為下標，將Redis BitMap中這些值設(shè)置為1锅睛。（我用的是jedis埠巨，具體方法不貼了網(wǎng)上有很多）
import com.yyhd.redisdemo.filter.BloomFilterHelper;
import com.yyhd.redisdemo.util.RedisUtil;
import lombok.AllArgsConstructor;
import org.springframework.stereotype.Component;
@Component
@AllArgsConstructor
public class BloomFilterUtil {
private final BloomFilterHelper bloomFilterHelper;
private final RedisUtil redisUtil;
public <T> void addBloomFilter(String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
redisUtil.setbit(key, i, true);
}
}
public <T> boolean includeByBloomFilter(String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
if (!redisUtil.getbit(key, i)) {
return false;
}
}
return true;
}
}
最后進行測試：
@RestController
@RequestMapping("/bloom")
@AllArgsConstructor
public class RedisController {
private final BloomFilterUtil bloomFilterUtil;
@GetMapping("/string/add")
public String redisString(String value){
boolean isExist = bloomFilterUtil.includeByBloomFilter("mobile", value);
System.out.println(value+ "是否存在：" + isExist);
if (!isExist) {
System.out.println("插入：" + value);
bloomFilterUtil.addBloomFilter("mobile", value);
}
return String.valueOf(isExist);
}
}
測試用例：
13333333333
13333333334
13333333335
13333333336
13333333337
13333333335
13333333337
輸出結(jié)果：
13333333333是否存在：false
插入：13333333333
13333333334是否存在：false
插入：13333333334
13333333335是否存在：false
插入：13333333335
13333333336是否存在：false
插入：13333333336
13333333337是否存在：false
插入：13333333337
13333333335是否存在：true
13333333337是否存在：true
