文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

什么是布隆过滤器?你学会了吗?

2024-11-30 20:44

关注

在对响应时间要求比较严格的情况下,如果我们有里面,那么随着集合中元素数量的增加,我们需要的存储空间越来越大,检索时间也越来越长,导致内存过多开销和时间效率变低。

这时候需要考虑的问题是,在数据量比较大的情况下,既能满足时间要求,又能满足空间要求,所以我们需要一种时间和空间消耗都比较小的数据结构和算法。布隆过滤器是一种解决方案。

什么是布隆过滤器?

Bloom Filter, 布隆过滤器由 Bloom于 1970 年提出。它实际上是一个长二进制向量和一系列随机映射函数, 布隆过滤器可用于检索元素是否在集合中。其优点是空间效率和查询时间远超一般算法,缺点是存在一定的误识别率和删除难度。根据它的特性,应用场景有如下:

布隆过滤器原理

布隆过滤器的原理是当一个元素加入到集合中时,通过K个哈希函数将该元素映射到一个位数组中的K个点,并将它们置为1。检索时,我们只需要看这些点是否都为1,就可以(大概)知道它是否存在于集合中。如果这些点中的任何一个有0,则检查的元素一定不存在。如果它们都是1,则被选中的元素很可能在那里。

Bloom Filter与单一哈希函数Bit-Map的区别在于,Bloom Filter使用k个哈希函数,每个字符串对应k个bits,从而降低碰撞概率。

由于Bloom filter只存储0和1而不存储具体值,所以在一些机密场合具有先天优势。位图的每一位都是一个位,所以通过位图有10亿个位置,位图的大小为0.12G,插入和查询的时间复杂度为O(k),k是哈希函数的个数。

布隆过滤器的问题

布隆过滤器之所以能够在时间和空间上取得比较高的效率,是因为它牺牲了判断的准确性和删除的便利性。

  1. 判断错误

有可能要找的元素不在容器中,但是散列后得到的k个位置都是1。如果布隆过滤器中存储了黑名单,则可以通过创建白名单来存储可能被误判的元素。

对于这个问题,可以通过增加位图数组的大小(位图数组越大,占用的内存越大)和减少哈希冲突来解决。但缺点是会增加占用的内存空间。

另一种解决方案是增加散列函数的数量并减少散列冲突。如果同一个键值等于一个函数,经过两个或多个哈希函数得到相等结果的概率自然会降低。然而,这会导致计算效率的降低,因为时间复杂度退化为O(hash times)。

  1. 难以去除

放置在容器中的元素映射到位数组的 k 个位置中的 1。删除的时候不能简单的直接设置为0,这样可能会影响其他元素的判断。你可以使用​​Counting Bloom Filter​​来解决这个问题。

Java中如何使用布隆过滤器

google的guava就提供了这样的API.

<dependency>
<groupId>com.google.guavagroupId>
<artifactId>guavaartifactId>
<version>22.0version>
dependency>

编写测试代码

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class GuavaBloomFilter {
public static void main(String[] args) {
int total = 1000000;
// default false positive ratefpp0.03
// fpp:There will always be a false positive rate in a Bloom filter
// Because hash collisions are impossible to avoid 100%.
// Bloom filter calls this misjudgment rate false positive probability,abbreviated as fpp
BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
// Initialize the total bar data into the filter
for (int i = 0; i < total; i++) {
bf.put("" + i);
}
// Determine whether the value exists in the filter
int count = 0;
for (int i = 0; i < total + 10000; i++) {
if (bf.mightContain("" + i)) {
count++;
}
}
System.out.println("Matched quantity " + count);

// Specified misjudgment rate: 1/10,000 to improve matching accuracy
BloomFilter<CharSequence> bfWithFpp = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);
for (int i = 0; i < total; i++) {
bfWithFpp.put("" + i);
}
int countFpp = 0;
for (int i = 0; i < total + 10000; i++) {
if (bfWithFpp.mightContain("" + i)) {
countFpp++;
}
}
//The smaller the value of the false positive rate fpp
// the higher the matching accuracy.
// When the value of the false positive rate fpp is reduced
// the storage space required is also larger
// Therefore, in actual use,
// a trade-off needs to be made between the false positive rate and the storage space.
System.out.println("The specified false positive rate has matched the number " + countFpp);// (1000001 - 1000000)/(1000000 + 10000) * 1000.0001
}
}


来源:JAVA旭阳内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯