Redis 实现布隆过滤器

昨天听马士兵教育张福刚讲公开课，里面讲解了布隆过滤器，今天无聊没事干，整理了一下笔记。关于布隆过滤器是什么东西，有什么应用场景就不做讨论了，网上有很多，大家可以自行了解，只记录实现：

1. pom 依赖

<dependency>  
<groupId>redis.clients</groupId>  
<artifactId>jedis</artifactId>  
<version>3.3.0</version>  
</dependency>

<dependency>  
<groupId>com.google.guava</groupId>  
<artifactId>guava</artifactId>  
<version>18.0</version>  
</dependency>

2. 具体实现

package cn.bridgeli.demo;

import com.google.common.hash.Funnels;  
import com.google.common.hash.Hashing;  
import org.junit.Before;  
import org.junit.Test;  
import redis.clients.jedis.Jedis;  
import redis.clients.jedis.JedisPool;  
import redis.clients.jedis.Pipeline;

import java.nio.charset.StandardCharsets;

/**  
* @author BridgeLi  
* @date 2020/6/6 16:38  
*/  
public class BloomFilter {

private Jedis jedis = null;

/**  
* 预估的数据量  
*/  
private static long n = 10000;

/**  
* 容忍的错误率  
*/  
private static double fpp = 0.01;

private static long numBits = optimalNumOfBits(n, fpp);  
private static int numHashFunctions = optimalNumOfHashFunctions(n, numBits);

/**  
* 根据预估数据量 n 和允许的错误率 fpp 计算需要的 bit 数组的长度  
*  
* @param n  
* @param fpp  
* @return  
*/  
private static long optimalNumOfBits(long n, double fpp) {  
if (0 == fpp) {  
fpp = Double.MIN_VALUE;  
}  
return (long) (-n \* Math.log(fpp) / (Math.log(2) \* Math.log(2)));  
}

/**  
* 根据预估的数据量和计算出来的需要的 bit 数组的长度，计算所需要的 hash 函数的个数  
*  
* @param n  
* @param numBits  
* @return  
*/  
private static int optimalNumOfHashFunctions(long n, long numBits) {  
return Math.max(1, (int) Math.round((double) numBits / n * Math.log(2)));  
}

/**  
* 预热数据  
*/  
@Before  
public void testBloomFilterBefore() {  
BloomFilter bloomFilter = new BloomFilter();  
bloomFilter.init();

for (int i = 0; i < n; i++) {  
bloomFilter.put("bf", String.valueOf(i + 100));  
}  
}

/**  
* 过滤数据  
*/  
@Test  
public void testBloomFilter() {  
BloomFilter bloomFilter = new BloomFilter();  
bloomFilter.init();

int ex_count = 0;  
int ne_count = 0;  
for (int i = 0; i < 2 * n; i++) {  
boolean exist = bloomFilter.isExist("bf", String.valueOf(i + 100));  
if (exist) {  
ex_count++;  
} else {  
ne_count++;  
}  
}

System.out.println("ex_count: " + ex_count + ", ne_count: " + ne_count);  
}

private void init() {  
JedisPool jedisPool = new JedisPool("127.0.0.1", 6379);  
jedis = jedisPool.getResource();  
}

public boolean isExist(String where, String key) {  
long[] indexs = getIndexs(key);

boolean result = false;  
try (Pipeline pipeline = jedis.pipelined()) {  
for (long index : indexs) {  
pipeline.getbit(where, index);  
}  
// 只要有一个位置为 false，即代表该数据不存在  
result = !pipeline.syncAndReturnAll().contains(false);  
} catch (Exception e) {

}

return result;  
}

public void put(String where, String key) {  
long[] indexs = getIndexs(key);

try (Pipeline pipeline = jedis.pipelined()) {  
for (long index : indexs) {  
pipeline.setbit(where, index, true);  
}  
pipeline.sync();  
} catch (Exception e) {

}

}

private long[] getIndexs(String key) {

long hash1 = Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(StandardCharsets.UTF_8)).asLong();  
long hash2 = hash1 >>> 16;

long[] result = new long[numHashFunctions];

for (int i = 0; i < numHashFunctions; i++) {  
long combinedHash = hash1 + i * hash2;  
if (combinedHash < 0) {  
combinedHash = ~combinedHash;  
}  
result[i] = combinedHash % numBits;  
}  
return result;  
}  
}