Advertisement

精心打造的数据结构系列——布隆过滤器（Bloom Filter）

阅读量：

前言

今天，我们将启动一个全新的专题——卓越设计中的数据结构。在这一系列中，我们将着重介绍一些令人赞叹的数据结构，这些内容与我们在大学阶段学习的《数据结构》课程有所不同。本系列所探讨的数据结构均源自学术界与工业界的深入研究，它们是在传统数据结构和经典算法基础上进行整合与创新的产物，因此在特定问题领域中展现出非凡的性能。

人们常说，计算机科学汇聚了全球最聪慧的头脑。无论是计算机初期的硬件设计，还是后期软件开发及算法研究，每一个环节都彰显出令人钦佩的智慧。

通过本系列的学习与探索，我们不仅可以在实际工作中直接应用这些新型数据结构，同时也能提升自身的研究思维能力。这有助于我们对传统数据结构和经典算法进行融合与创新，从而获得全新的问题解决方式。那么，让我们一同领略这些来自人类智慧结晶的独特魅力吧。

问题分析

在实际应用中，我们经常会面临这样的问题：如何在已有的数据集合中判断某个特定元素是否已经存在。具体的应用场景包括：

  • 云存储去重：当服务器准备存储新的文件时，需要先确认该文件是否已经被存储过
  • web缓存问题：为了提升用户访问的效率，web服务器通常会对高频访问的数据进行缓存处理。然而，随着数据的持续更新，缓存内容也需同步调整。因此，在决定是否将新数据写入缓存时，必须首先判断该数据是否已存在于缓存中

这类问题可以被简化描述为：当前维护着一个仅包含单一副本的数据集合，当有新的元素需要加入时，需在现有集合中判断该元素是否存在。
传统解决此类问题的方式通常是通过记录每个元素的摘要信息，并构建一个文件摘要表。当新元素到来时，只需将其摘要与表中的记录进行比对即可快速完成验证。然而，这种方法面临的主要挑战在于：随着数据集规模的扩大，摘要表也会随之线性增长，进而导致查询时间呈线性上升趋势。这不仅带来了较大的查询成本，在对摘要表进行索引等优化操作时还会产生额外的维护负担。

设计目标

鉴于此，有必要引入一种更为高效的数据结构与查询机制，以应对前述问题，同时所提出的解决方案需具备以下特性：

  • 在无需存储或泄露元素具体信息的前提下，完成对元素是否存在的判定
  • 尽可能将判定算法的时间复杂度维持在O(1)的水平
  • 确保判定过程中所需的存储资源与计算成本保持在较低的范围内

布隆过滤器

接下来，我们将重点介绍本研究的核心内容——布隆过滤器。首先，从最初的布隆过滤结构开始阐述，该结构最早由Bloom在1970年发表的文献[1]中提出。通过结合数组与多个独立的哈希函数构建完整框架，其基础模型主要涵盖三个过程：初始化设置阶段、数据集合录入阶段以及布隆过滤执行阶段。

模型初始化阶段设计

在这一阶段，用户需要预先设定所需数据集的规模m，以及所能接受的假阳性（false false）概率f（后续内容将对布隆过滤器中假阳性问题及其应对策略进行详细阐述）。
通过概率计算公式1：n=ceil(m / (-k / log(1 - exp(log( p ) / k))))
可得出初始化数组的容量n。
同时依据概率计算公式2：k=round((m / n) * log(2))
确定独立哈希函数的数量k。
最终，需构建一个长度为n的数组，并将所有元素初始化为0，同时准备k个相互独立的哈希函数以供后续初始化操作使用。
ps：还存在另一类需求，若已知数据集大小m、假阳性概率f以及独立哈希函数数量k，则可通过概率计算公式3来求解所需的初始化数组容量。

复制代码 
    lgp_k = Math.log(p) / k;	
    r = (-k) / Math.log(1 - Math.exp(lgp_k))
    n = Math.ceil(m / r)

数据集登记阶段

在这一阶段，需要对现有的数据集进行记录，针对数据集中的每个数据文件执行k次哈希计算，从而生成一个包含k个元素的哈希集合Hk。随后，对该集合进行逐项扫描，并将每个元素在数组中进行映射（可简化为执行&运算），最终将对应的映射位置标记为1。

布隆过滤阶段

在该阶段，需要对新增至数据集中的项目实施筛选与检测。通过重复数据登记流程，将每个项目进行k次独立的哈希运算，从而生成哈希集合Hk。随后对这一集合展开遍历操作，将每个元素映射到对应的数组位置上，并检查所有映射点是否为1。如果存在任一位置不为1，则可判定该元素并未存在于数据集中。

一个简单的例子

在未考虑假阳性出现可能性的前提下，对布隆过滤器进行简要演示：
首先创建三个文件f1、f2以及f3，其中f2为f1的复制版本，而f3则与f1、f2存在差异。假设数组容量设定为15，使用的独立哈希函数数量为3个，并采用以下优化策略，即使用HMAC函数结合对应的三个独立密钥来替代原本的三个独立哈希函数。
当文件f1被上传时，将执行哈希数组的初始化操作，具体算法如下：

复制代码 
    key1:jfwe30fm3o9z4
    key2:p0z9mc8d63n7
    key3:0k386fh36xl138
    HMAC(key1,f1) = 1024421  & 15 = 5
    HMAC(key2,f1) = 9102814  & 15 = 14
    HMAC(key3,f1) = 7819302 & 15 = 6
    布隆数组arr 0 0 0 0 0 1 1 0 0 0 0 0 0 1

在文件f2上传过程中，系统将执行去重校验操作，具体采用的算法如下：

复制代码 
    HMAC(key1,f2) = 1024421  & 15 = 5
    HMAC(key2,f2) = 9102814  & 15 = 14
    HMAC(key3,f2) = 7819302 & 15 = 6
    判断：哈希数组arr[5] == arr[14] == arr[6] == 1?
    结果：文件f2已经存在，不需要重复上传

在文件f3上传过程中，系统将执行去重检测操作，所采用的算法具体如下：

复制代码 
    HMAC(key1,f3) = 9810283  & 15 = 1
    HMAC(key2,f3) = 3219203  & 15 = 3
    HMAC(key3,f3) = 4864821 & 15 = 6
    判断：哈希数组arr[5] == arr[14] == arr[6] == 1?
    结果：文件f3不存在，需要进行上传，同时更新布隆数组
    更新结果arr 0 1 0 1 0 1 1 0 0 0 0 0 0 1

假阳性（false positive）分析

在传统《数据结构》课程中，对于散列表进行过探究的学生都清楚，散列表通过以空间换取时间的策略，在查找效率方面能够取得优异的表现，具体可实现O(1)的时间复杂度。然而，由于哈希函数本身的特性，设计机制中不可避免地出现了哈希碰撞的问题。理想情况下，不同的文件应当被合理且均匀地映射到数组的不同位置上。但由于哈希函数运算的不可预测性，不同文件常常被映射至相同的位置，从而引发一系列问题。针对散列表中的哈希碰撞问题，我们可以通过哈希再散列、线性探测等手段进行有效处理。

布隆过滤器同样面临类似的问题。原本不存在的文件可能因为其他文件的映射操作，导致其对应的所有位置都被标记为1，从而使用户误认为该文件存在，而实际上并不存在，这种现象被称为假阳性。目前，在布隆过滤器中尚未找到对假阳性问题的根本性解决办法。其产生的根本原因同样源于哈希函数的特性。因此，现有的解决方案只能围绕降低假阳性发生的概率展开：

  • 数组优化方案
    通过将数组依据独立哈希函数的数量进行划分，形成一个k维数组结构，并使每个独立哈希函数在对应的某一维数组上执行映射操作。这样可以分割原有的哈希映射空间，并有效减少碰撞发生的可能性。

  • 哈希运算优化方案
    在哈希运算方面存在两个优化方向：一方面可通过HMAC方式生成k个随机密钥，并基于这些密钥进行相应的哈希计算过程；这有助于减少对独立哈希函数数量的需求。另一方面可以选用生成较长摘要值的哈希算法，并将所生成的摘要平均划分为k部分后分别进行独立映射处理

参考文献综述

[1] B. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13:422-426, 1970.
[2] Almeida P S, Baquero C, Preguiça N, et al. Scalable Bloom Filters[J]. Information Processing Letters, 2007, 101(6):255-261.

Python代码推荐与实现

在上述所引用的文献[2]中，相关代码的编写工作是采用Python语言完成的，具体实现内容可通过提供的链接https://github.com/jaybaird/python-bloomfilter>进行查阅。

总结

截至目前，本系列的第一部分内容——关于布隆过滤器的学习已圆满完成。倘若各位同学能够认真研读并掌握上述内容，相信也会与我产生相同的感慨，这真是一种精妙且高效的数据结构。当然，任何看似完美的事物都不可避免地存在一些不足之处，布隆过滤器同样无法避免假阳性问题的存在。在这一过程中，如何实现误差与效率之间的平衡，也体现了一种策略性的思考与抉择。希望本次分享能让大家有所收获，如若有任何疑问，欢迎留言交流。

全部评论 (0)

还没有任何评论哟~

相关文章推荐