BloomFilter布隆过滤器 – 去当CTO

BloomFilter布隆过滤器

Posted on by zzcoder 阅读数：2,795

布隆过滤器：是一种空间效率极高概率性算法和数据结构，可以用来判断一个元素是否在集合中存在
因为是概率性的算法 及时判断存在的也有可能不存在 存在一定的误差，不适合用于“0误差”的场景中
布隆过滤器的原理：
空间占用小：不需要存储完整的元素，只需要对元素进行hash然后将bit向量表中的某个位设为1即可
查找效率高：直接对查询元素进行hash 然后看bit向量表中对应的位是否全是1
使用布隆过滤器的缺点：
1.因为存入的元素足够多 可能产生hash碰撞 不存在集合中的一定不存在，存在的不一定存在，可以通过多个hash函数减少误报的概率
2.不支持删除，维护困难
redis实现bloomfilter 可以利用redis的bitmap 方式实现分布式的布隆过滤器
具体实现方式我们可以参考google guava的实现方式
public static void main(String[] args) {
BloomFilter bloomFilter=BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),100000,0.001);
bloomFilter.put("jack");
System.out.println(bloomFilter.mightContain("jack"));
System.out.println(bloomFilter.mightContain("jac"));
}
通过预计的数组容量大小和误差率 来确定最后构建的容量和hash方法的个数
long numBits = optimalNumOfBits(expectedInsertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
return new BloomFilter(new BitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException var10) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", var10);
}
具体依据数组容量大小误差概率来计算多少个hash函数的算法
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int)Math.round((double)m / (double)n * Math.log(2.0D)));
}
具体计算数组容量大小的算法
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
if (p == 0.0D) {
p = 4.9E-324D;
}
return (long)((double)(-n) * Math.log(p) / (Math.log(2.0D) * Math.log(2.0D)));
}
其实都是利用了位图的bitmap的概念 Bit-map就是用一个bit位来标记一个元素对应的value，通过bit为单位来存储数据 大大的节省了存储空间
比如通过一个int型的整数的32比特位来存储32个10进制的数字比如要存入一个3 则如下所示 1100标识3
00000000000000000000000000001100
Redis的Bitmap是自动扩容的，亦即get/set到高位时，就会主动填充0。此外，还有bitcount指令用于计算特定字节范围内1的个数，bitop指令用来执行位运算（支持and、or、xor和not）
可以参考guava实现一个 redis的布隆过滤器 ，布隆过滤器使用的场景主要是过滤，也有使用在redis缓存穿透的场景中(不存在的数据进行过滤)
redis 数据库

11 thoughts on “BloomFilter布隆过滤器”

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 × 3 =