了解在数据库中的布隆过滤器原理
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,则意味着该元素存在于集合中。
- 点赞
- 收藏
- 关注作者
评论(0)