- 在VisualStudio中部署GDAL库的C++版本(包括SQLite、PROJ等依赖)
- Android开机流程介绍
- STM32CubeMX教程31USB_DEVICE-HID外设_模拟键盘或鼠标
- 深入浅出Java多线程(五):线程间通信
布隆过滤器,听过也学过,实际中没怎么用到,时间长了再接触这个概念就陌生了,说到底还是没有彻底掌握。为了真正理解一项技术或一个概念,最好还是从问题出发,所以布隆过滤器到底解决了什么问题呢?
布隆过滤器可以用来检测一个元素是否属于某个集合.
上面的定义比较抽象,下面有些具体的例子(参考这篇文章的内容:https://zhuanlan.zhihu.com/p/94433082):
从以上例子看,布隆过滤器确实很厉害,用处很多。不过如果我还没有这些项目的开发经验,怎么能用更通俗的方式理解布隆过滤器能解决什么问题呢? 最近悬疑剧看的多,我想到了破案这个场景.
警察破案,在寻找嫌疑人的时候,一般都会根据以下几种特征去筛查:
通常犯罪分子在犯罪之后都会潜逃到其他地方,警察需要一个个地方,甚至一个个城市去筛查,这个时候怎么样快速破案就成了一个关键问题。如果拿着嫌疑人的照片一个个去比对,显然太慢了,那么快速的方式是什么呢?假设我们有个“法外狂徒”张三,具备以下的特征:
特征 | 例子 | 0或1 |
---|---|---|
性别 | 男 | 1 |
性别 | 女 | 0 |
年龄 | 35 | 1 |
身高 | 175厘米 | 1 |
体重 | 70公斤 | 1 |
体型 | 偏瘦 | 1 |
肤色 | 黄色 | 1 |
发型 | 短发 | 1 |
眼睛颜色 | 黑色 | 1 |
脸型 | 方形 | 1 |
纹身 | 无 | 1 |
疤痕 | 左眼角有一道 | 1 |
习惯 | 喜欢喝咖啡 | 1 |
特点 | 话少 | 1 |
嗜好 | 喝酒 | 1 |
警察到了一个新的地方,会快速收集以上信息(通过公安系统或走访群众),判断一个区域内有没有人同时具备以上特征,如果没有,那犯罪嫌疑人肯定不在这个区域了,就可以继续排查下一个地方。如果发现该地区有人符合上述全部特征呢?那也并不代表一定就找到了嫌疑人,但是可以大大缩小排查的范围.
警察寻找嫌疑人的过程,不就是布隆过滤器的工作原理吗?
首先,警察寻找嫌疑人和上面列举的互联网产品中需要解决的问题都是一类问题:
例子 | 元素 | 集合 |
---|---|---|
警察寻找嫌疑人 | 嫌疑人 | 一个地区内的所有人 |
网页爬虫URL去重 | 一个URL | 是否在已经爬取的URL列表内 |
反垃圾邮件 | 一个邮箱地址 | 垃圾邮箱地址库 |
避免推荐给用户已经读过的文章 | 一篇文章 | 已经推荐给用户的文章集合 |
意查询请求带来的缓存穿透 | 请求所查询的商品 | 是否是商品库中真实存在的商品 |
警察会给嫌疑人列举一系列的特征,然后去看一个地区内是否有人具备所有这些特征。而布隆过滤器的原理是用哈希函数生成一个很长的0/1串,实际上我们可以把值为1的位置看作该元素具有这个位置的特征。接下来我们要去跟待筛选的集合进行比对,这个过程我们不需要一一比对,只需要去查看集合内是否有元素具备这个特征。这里我们需要维护两个向量:
内容 | 特征向量 | 例子 |
---|---|---|
元素 | 长度为N的向量,每个位置是0或1:1代表该元素具有该特征 | 嫌疑人一系列特征,1代表具有 |
集合 | 长度为N的向量,每个位置是0或1:1代表集合中存在一个元素具备这个特征 | 一个地区内人口的综合统计信息 |
接下来要做的就是比对这两个向量即可,而不是将元素和集合中的每个元素一一对比.
布隆过滤器的优点是查询速度快,缺点是不保证百分百准确。就好比说:即使我们在一个地方找到了符合所有犯罪嫌疑人特征的人,也有可能找错.
通过寻找犯罪嫌疑人的例子来理解布隆过滤器,可能更容易记住吧.
如果你喜欢我的文章,欢迎到我的个人网站关注我,非常感谢! 。
最后此篇关于布隆过滤器和寻找嫌疑人的文章就讲到这里了,如果你想了解更多关于布隆过滤器和寻找嫌疑人的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
题: 是否有一种简单的方法可以获取正在运行的应用程序中泄漏的资源类型列表? IOW 通过连接到应用程序? 我知道 memproof 可以做到,但它会减慢速度,以至于应用程序甚至无法持续一分钟。大多数任
正确地说下面的代码会将自定义日志发送到.net核心中的Docker容器的stdout和stderr吗? console.Writeline(...) console.error(..) 最佳答案 如果
我想将一个任务多次重复,放入 for 循环中。我必须将时间序列对象存储为 IExchangeItem , openDA 中的一个特殊类(数据同化软件)。 这是任务之一(有效): HashMap ite
我需要从文件中读取一个数组。该数组在文件中不是连续排序的,必须跳转“偏移”字节才能获得下一个元素。假设我读取一个非常大的文件,什么更有效率。 1) 使用增量相对位置。 2)使用绝对位置。 选项 1:
我有一个安装程序(使用 Advanced Installer 制作)。我有一个必须与之交互的应用程序,但我不知道如何找到该安装的 MSIHANDLE。我查看了 Microsoft 引用资料,但没有发现
我在替换正则表达式中的“joe.”等内容时遇到问题。这是代码 var objects = new Array("joe","sam"); code = "joe.id was here so was
我有 A 类。A 类负责管理 B 对象的生命周期,它包含 B 对象的容器,即 map。 ,每个 B 对象都包含 C 对象的容器,即 map .我有一个全局 A 对象用于整个应用程序。 我有以下问题:我
任何人都可以告诉我在哪里可以找到 freeImage.so 吗?我一直在努力寻找相同的东西但没有成功..任何帮助将不胜感激。我已经尝试将 freeimage.a 转换为 freeImage .so 并
在单元测试期间,我想将生成的 URL 与测试中定义的静态 URL 进行比较。对于此比较,最好有一个 TestCase.assertURLEqual 或类似的,它可以让您比较两个字符串格式的 URL,如
'find ./ -name *.jpg' 我正在尝试优化上述语句的“查找”命令。 在查找实现中处理“-name”谓词的方法。 static boolean pred__name __common (
请原谅我在这里的困惑,但我已经阅读了关于 python 中的 seek() 函数的文档(在不得不使用它之后),虽然它帮助了我,但我仍然对它的实际含义有点困惑,任何非常感谢您的解释,谢谢。 最佳答案 关
我在我正在使用的库中找到了这个语句。它应该检查集群中的当前节点是否是领导者。这是语句:(!(cluster.Leader?.IsRemote ?? true)) 为什么不直接使用 (cluster.L
我发现 JsonParser 在 javax.json.stream 中,但我不知道在哪里可以找到它。谁能帮帮我? https://docs.oracle.com/javaee/7/api/javax
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗?更新问题,使其仅关注一个问题 editing this post . 6年前关闭。 Improve this questi
如果 git 存储库中有新的更改可用,我有一个多分支管道作业设置为每分钟由 Jenkinsfile 构建。如果分支名称是某种格式,我有一个将工件部署到环境的步骤。我希望能够在每个分支的基础上配置环境,
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。 想改善这个问题吗?更新问题,使其成为 on-topic对于堆栈溢出。 6年前关闭。 Improve thi
我想我刚刚意识到当他们不让我使用 cfdump 时我的网络主机是多么的限制。这其实有点让我生气,真的,dump 有什么害处?无论如何,我的问题是是否有人编写了一个 cfdump 替代方案来剔除复杂类型
任务:我有多个资源需要在一个 HTTP 调用中更新。 要更新的资源类型、字段和值对于所有资源都是相同的。 示例:通过 ID 设置了一组汽车,需要将所有汽车的“状态”更新为“已售出”。 经典 RESTF
场景:表中有 2 列,数据如下例所示。对于“a”列的相同值,该表可能有多个行。 在示例中,考虑到“a”列,“1”有三行,“2”有一行。 示例表“t1”: |a|b ||1|1.1||1|1.2||1
我有一个数据框: Date Price 2021-01-01 29344.67 2021-01-02 32072.08 2021-01-03 33048.03 2021-01-04 32084.
我是一名优秀的程序员,十分优秀!