【数据结构与算法】什么是布隆过滤器?如何防止缓存穿透的问题?
发布日期:2021-06-29 15:36:08
浏览次数:3
分类:技术文章
本文共 681 字,大约阅读时间需要 2 分钟。
布隆过滤器(Bloom Filter)
背景
如果要经常判断1个元素是否存在,你会怎么做?
- 很容易想到使用哈希表(HashSet、HashMap),将元素作为key去查找
- 时间复杂度:O(1), 但是空间利用率不高,需要占用比较多的内存资源
但如果需要编写一个网络爬虫去爬10亿个网站数据,为了避免爬到重复的网站,如何判断某个网站是否爬过?
- 很显然HashSet、HashMap并不是非常好的选择
那么是否存在时间复杂低、占用内存较少的方案?
- 布隆过滤器(Bloom Filter)
布隆过滤器(Bloom Filter)
布隆过滤器是1970年由布隆提出,它是一个空间效率高的概率型的数据结构,可以用来告诉你:一个元素一定不存在或者可能存在;
优缺点:
- 优点:空间效率和查询时间都远远超过一般的算法
- 缺点:有一定的误判率、删除困难
它本质上是一个很长的二进制向量和一系列随机映射函数(Hash函数)
常见应用:
- 网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题
布隆过滤器的原理
假设布隆过滤器由20位二进制、3个哈希函数组成,每个元素经过哈希函数处理都能生成一个索引位置;
- 添加元素:将每一个哈希函数生成的索引位置都设置为1;
- 查询元素是否存在:
- 如果有一个哈希函数生成的索引位置不为1,就代表不存在(100准确);
- 如果每一个哈希函数生成的索引位置都为1,就代表存在(存在一定的误判率);
- 添加、查询的时间复杂度都是O(k),k是哈希函数个数
布隆过滤器的误判率
加、查询的时间复杂度都是O(k),k是哈希函数个数
布隆过滤器的误判率
转载地址:https://codingchaozhang.blog.csdn.net/article/details/115430578 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月02日 22时52分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【PYTHON】yield和return的不同
2019-04-29
用 Python 开发 DeFi 去中心化借贷应用(下)
2019-04-29
Python 为什么引入这两个关键词
2019-04-29
Python 时间序列预测:Hot-winters
2019-04-29
importlib.import_module() 和import
2019-04-29
Pycharm connecting to console的解决方案
2019-04-29
typehints
2019-04-29
样本不均衡、长尾分布问题的方法整理(文献+代码)
2019-04-29
计算机视觉哪个方向最火?来看这篇综述《中国图像工程:2020》
2019-04-29
格式化字符串(%s,%d,%r)
2019-04-29
python的map()
2019-04-29
python的filter()函数
2019-04-29
1239.串联字符串的最大长度 关于字符串的回溯算法!
2019-04-29
力扣每日一题:525.连续数组 前缀和+hash表速解!
2019-04-29
Python堆排序介绍与力扣三道堆相关题目分享
2019-04-29
python 两个栈实现一个队列 && 两个队列实现一个栈
2019-04-29
力扣每日一题:523.连续的子数组和 前缀和+哈希表解法
2019-04-29
1642.可以到达的最远建筑 神偷Jacky的思路带你分析贪心+堆操作!
2019-04-29
5781.删除一个字符串中所有出现的给定子字符串 有趣的三种解法!
2019-04-29