布隆过滤器(Bloom Filter)是1970年由布隆提出的。他对判断海量元素是否存在的问题进行了研究,也就是到底需要多大的位图和多少个哈希函数发表了一篇论文,提出的这个容器就叫做布隆过滤器。
优点:
相比其他的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器的插入、查询时间复杂度都是O(N)。
布隆过滤器不需要存储元素本身,所以保密性有保证。
缺点:
随着存入元素数量的增加,误算率随之增加。
很难删除其中元素。
布隆过滤器的使用我使用的是guava的布隆过滤器,先学习学习怎么用。
public class BloomFilterTest {
private static Integer expectedInsertions = 10000000;
private static Double fpp = 0.001;
private static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
public static void main(String[] args) {
// 插入 1千万数据
for (int i = 0; i < expectedInsertions; i++) {
bloomFilter.put(i);
}
// 用1千万数据测试误判率
int count = 0;
for (int i = expectedInsertions; i < expectedInsertions * 2; i++) {
if (bloomFilter.mightContain(i)) {
count++;
}
}
System.out.println("一共误判了:" + count);
System.out.println("误判率:" + (100.0 * count / expectedInsertions) + "%");
}
}
结果
实现原理我们都知道hashMap,其实布隆过滤器跟hashMap有一定的相似性。
但是hashMap的hash碰撞几率太大了,我们就得优化。怎么优化呢,如果觉得家里不安全,我们就给门加锁,不怕麻烦就多加几把锁,减少别人的钥匙能开我家门的可能性。
这样是不是碰撞的几率就小了。校验是否存在时,也是把多把钥匙拿出来,试一试能不能开这个门。
源码分析源码中有四个私有变量
// 存储数据映射的数组/bitmap:长度根据预估数据量和误判率计算,其中误判率与数组大小成反比。 private final LockFreeBitArray bits; // 执行hash算法的次数:根据bits数组长度和预估数据量计算,与误判率成反比。 private final int numHashFunctions; // 数据类型 private final Funnel super T> funnel; // hash算法 private final BloomFilter.Strategy strategy;
put的流程,经过numHashFunctions次hash,每次都去寻找存放位置,看是否有效,有效就对应累加。
mightContain的流程,经过numHashFunctions次hash,每次都去寻找存放位置,看是否有效,经过numHashFunctions次hash如果每次都有效就证明存在。
public实际应用场景boolean put(@ParametricNullness T object, Funnel super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) { long bitSize = bits.bitSize(); byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal(); long hash1 = this.lowerEight(bytes); long hash2 = this.upperEight(bytes); boolean bitsChanged = false; long combinedHash = hash1; // 经过numHashFunctions次hash for(int i = 0; i < numHashFunctions; ++i) { bitsChanged |= bits.set((combinedHash & 9223372036854775807L) % bitSize); combinedHash += hash2; } return bitsChanged; } public boolean mightContain(@ParametricNullness T object, Funnel super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) { long bitSize = bits.bitSize(); byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal(); long hash1 = this.lowerEight(bytes); long hash2 = this.upperEight(bytes); long combinedHash = hash1; for(int i = 0; i < numHashFunctions; ++i) { // 如果bitmap中没有对应值则认为没有该值,返回false if (!bits.get((combinedHash & 9223372036854775807L) % bitSize)) { return false; } combinedHash += hash2; } return true; }
(1) 典中典就是缓存穿透。
(2) 垃圾邮件的过滤,通过把垃圾邮件地址加入布隆过滤器,当布隆过滤器判定地址存在于垃圾地址列表,再去进行校验。



