首页 > 其他分享 >BloomFilter总结

BloomFilter总结

时间:2023-07-03 15:24:10浏览次数:31  
标签:总结 slot hash 函数 value bitArray BloomFilter

BloomFilter是用来判断,某元素是否曾经来访过的有状态数据结构。
优点:

1.写入、查询效率都非常高,得益于元素在写入、查询的寻址过程,采用的都是n个hash函数,其时间复杂度是O(1).
2.另外,底层用于存储状态的是bitArray结构,非常省空间。

缺点:

1.对于两个不同元素,由于hash碰撞无法避免,且底层用的bit表示状态,所以通过n个hash函数计算后可能落在相同的slot上。所以结果只是一个概率性的表征,不保证百分百的准确。

  1. 初始化时:底层bitArray每个slot的vavlue默认全为0
  2. 插入时:将元素e,经过n个不同的hash函数计算,散落到bitArray上的n(若不同hash函数的计算结果发生重复,可能小于n)个slot上,对应slot上的value设为1
  3. 查询时:将元素e,经过n个不同的hash函数计算,对应到bitArray上的slot,分别取出这些slot上的value,若全部value都为1,则返回true,否则返回false。

标签:总结,slot,hash,函数,value,bitArray,BloomFilter
From: https://www.cnblogs.com/JaxYoun/p/17522965.html

相关文章

  • 22年11月Tita升级「总结」细节优化升级
    升级详情Tita-OKR和新绩效一体化管理平台一、【OKR列表】新增目标类别、目标状态、目标风险筛选周期筛选后的高级筛选中,可找到新增的筛选项,快捷查看关注的信息二、 【OKR仪表盘】新增目标类别与目标状态筛选周期后新增高级筛选,可选择统计不同类别、状态的OKR三......
  • Shopee面经总结
    面经1消息队列如何保证可靠性消息队列如何保证消息幂等性消息队列的优缺点为什么用b+树聚集索引和主键区别,其他引擎怎么做的平时数据库编码explain参数http报文参数有哪些吗?做题,链表奇偶有序输出面经2自我介绍有哪些排序算法?介绍下快排/堆排/归并排序。数据库中......
  • 7.2总结
    早上起的比较晚,就没有赶上吃早饭,自己吃的泡面,吃完泡面就玩了会游戏,玩了一会就狠狠的刷科一的题,刷了起码两个小时,真的麻了,中午做了个饭,天气是真的热啊,出一身的汗吃了个午饭就眯了一下小会儿,又看科一的题,看模拟题做的真难,跟本就就不能及格,下午就收拾收拾家里,就做的晚饭吃,吃完学习了......
  • 假期第二周每周总结
    本周,主要进行数据库的作业练习,主要攻克前端的界面问题,主要一个靠爬,但是也有很多的问题,解决不了,所以就利用可视化的工具进行简单实现,以下为界面:  在数据库设计的过程中,我学到了很多关于设计、规划和管理数据库的重要原则和技巧。通过实践和研究,我成功地完成了一个数据库设......
  • 每日总结1
    一.今天干了什么第一天,和朋友打了王者,总.结下来,一颗星也没多,为了让我妹晚上睡觉不哭,带她说了一天,不她睡午觉,还始我妹妹洗了澡二.遇到的问题,打算怎么解决无三.明天准备干什么打游戏,学习java内容......
  • 【考后总结】7 月多校国赛模拟赛 1
    7.2冲刺国赛自测9T1字符串一个合法位置\([l,r]\)代表\([1,x]\)与\([l,l+x-1]\)相同,\([y,n]\)与\([r-y+1,r]\)相同,类似\(x\in\mathrm{Border}(l+x-1)\)。对正反串做KMP,建失配树,类似要求\(x\)子树和\(y\)子树的交,而\((l+x-1)+1=(r-y+1)\)所以正串失配树子树......
  • 2023年暑假集训总结
    2023年暑假集训总结/6.26-背锅的chara-博客园(cnblogs.com)2023年暑假集训总结/6.27-背锅的chara-博客园(cnblogs.com)2023年暑假集训总结/6.28-背锅的chara-博客园(cnblogs.com)2023年暑假集训总结/6.29-背锅的chara-博客园(cnblogs.com)2023年暑假集训......
  • 【考后总结】7 月多校国赛模拟赛 1
    7.2冲刺国赛自测9T1字符串一个合法位置\([l,r]\)代表\([1,x]\)与\([l,l+x-1]\)相同,\([y,n]\)与\([r-y+1,r]\)相同,类似\(x\in\mathrm{Border}(l+x-1)\)。对正反串做KMP,建失配树,类似要求\(x\)子树和\(y\)子树的交,而\((l+x-1)+1=(r-y+1)\)所以正串失配树子树......
  • SSTI 总结
    写给自己的不过多的去讲解其他的东西了这里是一个ssti的实例其实ssti造成漏洞的成因就是把模板中带有{{带有这类字符之后进行了一个编译渲染把里面的东西当成了代码去执行fromflaskimportFlask,request,render_template_stringapp=Flask(__name__)@app.route(......
  • 7.2 周日总结
    周日十点起床,收拾卧室,吃完午饭睡觉,三点起来刷科一,四点到四点半看《大道至简》,四点半以后看了《跳进地理书的旅行》,太好看了!和许红豆联动,双厨狂喜。五点去接妹妹放假,七点去吃饭,现在刚回来,一会洗完澡看java视频。......