如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果检查到一个元素不在集合中，那肯定就不在。如果计算到在集合中，虽然也有一定的错误率，但是错误率还是比较低的。
以上内容来自百度百科《布隆过滤器》词条，阐述了bloomfilter的基础原理。BloomFilter常被用于需要唯一性校验的场景，如爬虫等。
java中有许多bloomfilter的实现包，最常用的还是guava中的BloomFilter。但是现在的应用多存在分布式部署的现象，本地的BloomFilter实现已经不能满足需求了，我们需要一个分布式BloomFilter实现。redis的Bitmap是实现分布式BloomFilter的一个好基础。
首先，我们需要计算一个字符串的不同Hash值的方案，这里准备了一个BloomFilterHelper类：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
import org.apache.commons.codec.digest.MurmurHash3; public class BloomFilterHelper { private final int bitSize; private final int numHashFunctions; public BloomFilterHelper(int expectedInsertions, double fpp) { // 计算bit数组长度 bitSize = optimalNumOfBits(expectedInsertions, fpp); // 计算hash方法执行次数 numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize); } /** * 计算offset */ public int[] murmurHashOffset(String value) { int[] offset = new int[numHashFunctions]; long hash64 = hash64(value); 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数组长度 */ private int optimalNumOfBits(long n, double p) { if (p == 0) { // 设定最小期望长度 p = Double.MIN_VALUE; } return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); } /** * 计算hash方法执行次数 */ private int optimalNumOfHashFunctions(long n, long m) { return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); } /** * 执行hash64运算 * * @param value 值 * @return hash计算结果 */ private long hash64(String value) { long[] result = MurmurHash3.hash128x64(value.getBytes()); return result[0]; } } |
BloomFilterHelper类的构造器需要传入两个参数：expectedInsertions 和 fpp。
- expectedInsertions ： 预期写入的字符串总数
- fpp ：误判率
误判率当然是越低越好，但是也意味着要为存储的数据准备更多的空间，但redis的Bitmap天然是有上限的，因此需要根据实际情况做最优设计。
另外，这里使用了commons-codec这个包来计算字符串的hash值。采用的是Murmur hash64计算。
然后是向redis的Bitmap中写入相应信息：
|
1 2 3 4 5 6 7 8 9 |
public void multiSetBit(final String key, boolean value, int... offsets) { redisTemplate.executePipelined((RedisCallback<Object>) connection -> { byte[] bytes = key.getBytes(); for (long offset : offsets) { connection.setBit(bytes, offset, value); } return null; }); } |
最后是要验证字符串对应的offset是否在Bitmap中。下面是从Bitmap中取值的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public List<Boolean> multiGetBit(String name, int... offsets) { List<Object> results = redisTemplate.executePipelined((RedisCallback<Object>) connection -> { for (long offset : offsets) { connection.getBit(name.getBytes(), offset); } return null; }); List<Boolean> list = new LinkedList<>(); results.forEach(obj -> list.add((Boolean) obj)); return list; } |
以及相应的校验代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public boolean check0(String key, int[] offsets) { List<Boolean> list = redisClient.multiGetBit(key, offsets); for (Boolean b : list) { if (!b) { return false; } } return true; } public boolean checkAndSet(String value) { String key = new SimpleDateFormat("yyyyMMdd").format(new Date()); long ttl = redisClient.ttl(key, TimeUnit.MILLISECONDS); if (ttl < 0) { redisClient.expire(key, 1, TimeUnit.DAYS); } int[] offsets = bloomFilterHelper.murmurHashOffset(value); boolean r = check0(key, offsets); redisClient.multiSetBit(key, true, offsets); return r; } |
大体上就是这些内容了。
完整代码在GitHub：zhyea / springboot-redis。
End！
发表评论