关于后端:浅聊一下-布隆过滤器

3次阅读

共计 1755 个字符，预计需要花费 5 分钟才能阅读完成。

明天咱们来聊一聊布隆过滤器，理解他之前，咱们先看一看是干什么用的

百度百科解释他能够判断一个元素是否在汇合中，前面还说了他的效率呀什么的都很好，那既然如此，咱们再设想一下为什么须要它！

针对上述问题，如果咱们间接任由申请拜访数据库，问题 1、2 还行，如果是问题 3，那数据库大抵要说栓 Q 了。既然如此，咱们联合刚刚看到的布隆过滤器正好是用来判断一个元素是否存在汇合中。而且它的长处就是空间效率、查问工夫都比他人要好的多。那不得看看他到底是咋好的撒。

别急！先骗一波关注！骗不到也没事，咱也不小心眼，接着往下说；

如何实现高效率的判断一个元素在不在汇合中呢！有的小伙伴立即就联想到了 List.contains() 办法。如果光靠这个办法，在数据量较大的状况，还是会存在效率问题

依据源码咱们能够看到他是挨个遍历的，象征每次都要遍历全量的汇合。那既然每次都要遍历整个汇合，那有什么方法呢？

把汇合长度变短！对！布隆过滤器就是这样干的，那元素怎么放呢？

咱们能够把任意一个须要比拟的元素，通过函数，生成 2 个或 3 个甚至更多个整数。情理大抵和 hash 差不多，只不过这里是生成多个整数

咱们如果二进制向量的长度为 9，散列函数的个数为 3 的布隆过滤器，针对 元素 X ，三个不同的散列函数别离生成的哈希值为 1，4，8。则上图转变为：

同理，咱们再存一个 元素 Y ，如果散列函数返回 4，6，9 的话，图变为：

假如，咱们要判断元素 Z，此时通过计算哈希返回 1，4，5 的话，发现其中 5 为 0，就能够判断元素 Z 不存在此容器中。

由此咱们能够主观的判断出其优缺点：

长处：

空间占用极小，因为自身不存储数据而是用比特位示意数据是否存在，某种程度有窃密的成果。
插入与查问工夫复杂度均为 O(k)，常数级别，k 示意散列函数执行次数
散列函数之间能够互相独立，能够在硬件指令层减速计算。

毛病：

误差（假存在性）
无奈删除

布隆过滤器能够 100% 的判断元素不在汇合中，然而当汇合元素十分多都为 1 时，此时散列函数凑巧又生成了存在的值，就能够判断为假性存在（假阳性）

如何解决误差问题

在创立布隆过滤器时咱们为了找到适合的 m 和 k，能够依据预期元素数量 n 与 ε 来推导出最合适的 m 与 k

位数组长度 m
散列函数个数 k
预期元素数量 n
冀望误差 ε

算法实现：

// 计算哈希次数
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {// (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
 
// 计算位数组长度
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {if (p == 0) {p = Double.MIN_VALUE;}
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

这样咱们就能够迷信的确定数组长度、散列个数。

咱们来看下一个问题

无奈删除！

布隆过滤器判断一个元素存在就是判断对应地位是否为 1 来确定的，然而如果要删除掉一个元素是不能间接把 1 改成 0 的，因为这个地位可能存在其它元素，所以如果要反对删除，那咱们应该怎么做呢？

最简略的做法就是加一个计数器，就是说位数组的每个位如果不存在就是 0，存在几个元素就存具体的数字，而不仅仅只是存1。那么这就有一个问题，原本存1 就是一位就能够满足了，然而如果要存具体的数字比如说 2，那就须要2 位了，所以 带有计数器的布隆过滤器会占用更大的空间。

参考资料:

布隆过滤器如何删除 -https://www.kancloud.cn/zatko…

布隆过滤器原理实现 -https://blog.csdn.net/jfwan/a…

百度百科 https://baike.baidu.com/item/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8/5384697-https://baike.baidu.com/item/…

最初给点个关注吧

关注『Xiang 想』公众号

本文由 mdnice 多平台公布

正文完