大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
1、布隆过滤器是什么?(判断某个key一定不存在)
-
本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构
-
特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。
-
相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。
使用:
1. 布隆过滤器在NoSQL数据库领域中应用的非常广泛
2. 当用户来查询某一个row时,可以先通过内存中的布隆过滤器过滤掉大量不存在的row请求,然后去再磁盘进行查询
3. 布隆过滤器说某个值不存在时,那肯定就是不存在,可以显著降低数据库IO请求数量
2、应用场景
1)场景1(给用户推荐新闻)
-
当用户看过的新闻,肯定会被过滤掉,对于没有看多的新闻,可能会过滤极少的一部分(误判)。
-
这样可以完全保证推送给用户的新闻都是无重复的。
2)场景2(爬虫url去重)
-
在爬虫系统中,我们需要对url去重,已经爬取的页面不再爬取
-
当url高达几千万时,如果一个集合去装下这些URL地址非常浪费空间
-
使用布隆过滤器可以大幅降低去重存储消耗,只不过也会使爬虫系统错过少量页面
3、布隆过滤器原理
-
每个布隆过滤器对应到Redis的数据结构是一个大型的数组和几个不一样的无偏hash函数
-
如下图:f、g、h就是这样的hash函数(无偏差指让hash映射到数组的位置比较随机)
添加:值到布隆过滤器
-
1)向布隆过滤器添加key,会使用 f、g、h hash函数对key算出一个整数索引,然后对长度取余
-
2)每个hash函数都会算出一个不同的位置,把算出的位置都设置成1就完成了布隆过滤器添加过程
查询:布隆过滤器值
-
1)当查询某个key时,先用hash函数算出一个整数索引,然后对长度取余
-
2)当你有一个不为1时肯定不存在这个key,当全部都为1时可能有这个key
-
3)这样内存中的布隆过滤器过滤掉大量不存在的row请求,然后去再磁盘进行查询,减少IO操作
删除:不支持
-
1)目前我们知道布隆过滤器可以支持 add 和 isExist 操作
-
2)如何解决这个问题,答案是计数删除,但是计数删除需要存储一个数值,而不是原先的 bit 位,会增大占用的内存大小。
-
3)增加一个值就是将对应索引槽上存储的值加一,删除则是减一,判断是否存在则是看值是否大于0。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188256.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...