了解在数据库中的布隆过滤器原理

举报
码乐 发表于 2024/05/27 10:30:02 2024/05/27
【摘要】 1 简介布隆过滤器是一种节省空间的方式,用来存储有关键列表的信息。在其中,有一个位图和一个哈希函数。计算存储在 SST 中的键的哈希值,并将结果用于将位图中的某些位设置为“1”。当您想知道列表中是否存在某个键时,您可以通过哈希函数运行它并检查位图中的相应位是“1”还是“0”。如果其中一个位是“0”,您确定该密钥不在列表中。如果所有位均为“1”,则可能存在该值。误报的概率仅取决于几个因素:位...

1 简介

布隆过滤器是一种节省空间的方式,用来存储有关键列表的信息。
在其中,有一个位图和一个哈希函数。

计算存储在 SST 中的键的哈希值,并将结果用于将位图中的某些位设置为“1”。当您想知道列表中是否存在某个键时,您可以通过哈希函数运行它并检查位图中的相应位是“1”还是“0”。

如果其中一个位是“0”,您确定该密钥不在列表中。如果所有位均为“1”,则可能存在该值。误报的概率仅取决于几个因素:

位图的大小
列表中的键数
每个键值设置为“1”的位数

布隆过滤器是具有空间效率和概率性的独特属性的数据结构。我们将在博客后面详细介绍这两个属性。

2 两个概念

为了更好地了解布隆过滤器,让我们阅读布隆过滤器所依赖的 2 个概念。

  • 位数组

它是一种数组数据结构,其中仅存储布尔值。它用于将位数组中某个域的值与 {0, 1} 映射

    []  []  []  []  []
     1   2   3   4   5
  • 哈希函数
    哈希函数与任何其他函数一样,接受输入并应用一些算法将输入更改为称为哈希值的输出。

    输入 --> 哈希函数 SHA-1 —> 哈希值

哈希值有多种应用,最常见的应用之一是将哈希值存储在哈希表中以加快检索速度。应用于转换输入的算法的一个示例是 SHA-1。

哈希函数的特性使其成为将其用于布隆过滤器的理想选择:

无论输入是什么,输出的长度都保持不变。
每次传递相同的输入时,它都会给出相同的输出。
您可以阅读有关哈希函数的更多信息这里打开一个新窗口.

3 它是如何工作的?

为了了解布隆过滤器的工作原理,让我们举一个用例,我们想在位数组中存储单词“Marvel”。

让我们将其工作分解为几个步骤。

初始化位数组。
将参数传递到一组哈希函数中。
收集每个哈希函数的输出。
应用一些数学逻辑来获取要更新的位,在我们的例子中,我们使用模运算。
使用值 1 更新上一步中获得的位。
让我们看一下图表,看看同样的过程在运行。

我们已经初始化了大小为 100 的位数组,默认值为 0。

[] [] [] ... []
 1  2  3     100

将参数传递给一组哈希函数。 函数进行一些输出

输入 --->  哈希函数  ---> 4456326
	--->  哈希函数   ---> 4456326
	...

现在我们将模运算应用于哈希函数的每个输出,我们将通过位数组的大小对其进行调制。

这些是我们需要更新以将“Marvel”存储在位数组中的位。

[1] [0] [1] [1] [0] [0] [0] [0] [0] [0]
 1   2   3   4   5   6   7   8   9   10

4 小结

布隆过滤器是一种空间高效的的数据结构,用于判断一个元素是否可能在一个集合中。它包含一个位图和多个哈希函数。哈希函数将键映射到位图的特定位置,设置为1。

查询时,通过同样哈希函数检查位图,全1则可能存在,有0则肯定不存在。误报概率与位图大小、键数量和哈希位数相关。其工作流程包括初始化位数组、应用哈希函数、更新位数组。

布隆过滤器在存储和查找时利用位数组和哈希函数的特性,实现概率性查找。
现在,如果我们想在布隆过滤器中搜索任何单词,我们遵循相同的过程,除了不是用 1 更新位,而是在这些位中获取存储的值,如果所有值均为 1,则意味着该元素存在于集合中。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。