专栏首页编码前线布隆过滤器(Bloom Filter)详解

布隆过滤器(Bloom Filter)详解

直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中。 和一般的hash set不同的是,这个算法无需存储key的值,对于每个key,只需要k个比特位,每个存储一个标志,用来判断key是否在集合中。

算法: 1. 首先需要k个hash函数,每个函数可以把key散列成为1个整数 2. 初始化时,需要一个长度为n比特的数组,每个比特位初始化为0 3. 某个key加入集合时,用k个hash函数计算出k个散列值,并把数组中对应的比特位置为1 4. 判断某个key是否在集合时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

优点:不需要存储key,节省空间

缺点: 1. 算法判断key在集合中时,有一定的概率key其实不在集合中 2. 无法删除

基本概念

如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢。不过世界上还有一种叫作散列表(又叫哈希表,Hash table)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit Array)中的一个点。这样一来,我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设 Hash 函数是良好的,如果我们的位阵列长度为 m 个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了(Space-efficient)。解决方法也简单,就是使用多个 Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率是比较低的。

优点

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

k 和 m 相同,使用同一组 Hash 函数的两个布隆过滤器的交并差运算可以使用位操作进行。

缺点

但是布隆过滤器的缺点和优点一样明显。误算率(False Positive)是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

False positives 概率推导

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位,m 是该位数组的大小,k 是 Hash 函数的个数,那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是:

那么在所有 k 次 Hash 操作后该位都没有被置 "1" 的概率是:

如果我们插入了 n 个元素,那么某一位仍然为 "0" 的概率是:

因而该位为 "1"的概率是:

现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 "1",但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中(False Positives),该概率由以下公式确定:

其实上述结果是在假定由每个 Hash 计算出需要设置的位(bit) 的位置是相互独立为前提计算出来的,不难看出,随着 m (位数组大小)的增加,假正例(False Positives)的概率会下降,同时随着插入元素个数 n 的增加,False Positives的概率又会上升,对于给定的m,n,如何选择Hash函数个数 k 由以下公式确定:

此时False Positives的概率为:

而对于给定的False Positives概率 p,如何选择最优的位数组大小 m 呢,

上式表明,位数组的大小最好与插入元素的个数成线性关系,对于给定的 m,n,k,假正例概率最大为:

本文分享自微信公众号 - 编码前线(gh_acef1225aadd)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JAVA面试50讲之5:Vector,ArrayList,LinkedList的区别

    一组”对立”的元素,通常这些元素都服从某种规则   1.1) List必须保持元素特定的顺序   1.2) Set不能有重复元素   1.3) Queue保持一...

    用户1205080
  • Spark-RDD常用Transformationg与Action操作

    RDD创建后就可以在RDD上进行数据处理。RDD支持两种操作:转换(transformation),即从现有的数据集创建一个新的数据集;动作(action),即...

    用户1205080
  • Java优先队列(PriorityQueue)示例

    我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时段生成股...

    用户1205080
  • Java集合框架一览笔录

    1、集合概念 集合类主要负责保存、盛装其他数据,因此集合类也被称为容器类。所以的集合类都位于java.util包下,后来为了处理多线程环境下的并发安全问题,ja...

    斯武丶风晴
  • 人人都是产品经理 : 如何写出一份优秀的 PRD ? 精于心简于形 !

    一个好的prd框架结构应该至少包含以下内容:产品简介、产品概览、产品架构、产品原型、非功能性需求,如下图:

    一个会写诗的程序员
  • Java:那些关于集合的知识都在这里了!

    在本节中,会先介绍Collection接口,再介绍其具体集合实现类(List、Set、Queue类)

    Carson.Ho
  • 大数据计算:Storm vs Flink

    大数据技术中常见的大数据实时计算引擎有Spark、Storm、Flink等,目前有很多公司已经将计算任务从旧系统 Storm 迁移到 Flink。

    加米谷大数据
  • sed命令实例

    sed命令行格式为: sed [-nefri] 'command 输入文本 常用选项: - -n∶使用安静(silent)模式。在一般 sed 的用法中,...

    程裕强
  • Squid代理服务器应用示例

    L宝宝聊IT
  • Squid 服务的安装及部署

    squid 作为一款服务器代理工具,可以缓存网页对象,减少重复请求,从而达到加快网页访问速度,隐藏客户机真实IP,更为安全。 squid的工作机制:

    小手冰凉

扫码关注云+社区

领取腾讯云代金券