开篇思考
一般我们用来判断一个元素是否存在,会想到用 List,Map,Set 等,会将元素先保存下来,然后进行筛选。
但是这样的形式都有一个弊端就是一定要保存数据才行,可是我们仅仅想知道是否存在数据,并不要求获取实际数据,
这时候就会觉得这种方式实在是浪费空间。
什么情况下我们只需要判断是否存在这个元素呢?
在系统设计的时候,我们会考虑大量并发的形式,但是很多请求可能是在访问不存在的数据,
那么我们就没有必要继续这个请求,可以在 API 网关层就直接过滤掉。
Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,
被用来检测一个元素是不是集合中的一个成员。
布隆过滤器实现是不保存数据本身,而是通过 K 个 hash 函数来计算在 byte[] 数组中的存放位置,
并把这个位置的值设置为 1, 而这个 K 到底是多少个呢,要根据公式来算出,待会列出。
除了这个 K 值,我们还要计算 byte[] 数组的长度 m ,下面一并列出计算公式:
下面我们以数字 11 为例来使用,有个网站可以测试布隆过滤器,
优点:
缺点:
这个其实在 google guava 包中有现成的实现,不用我们自己去实现。我们看看是怎么实现的;
/**
* 计算 bit 数组的长度公式
* n : 预估数据量
* p : 误差率 0-1
*/
@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)));
}
/**
* 计算 hash 函数个数的方法
* n : 预估数据量
* m : bit 数组长度
*/
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int)Math.round((double)(m / n) * Math.log(2.0D)));
}
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterTest {
public static void main(String[] args) {
int expectedInsertions = 800000000;
double fpp = 0.00001;
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), expectedInsertions, fpp);
int i = 10000;
while (i > 1){
bloomFilter.put("aa" + i);
System.out.println(bloomFilter.mightContain("ab" + i));
i--;
}
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。