美文网首页我爱编程
简单、高效的数据结构--Bloom Filter(布隆过滤器)

简单、高效的数据结构--Bloom Filter(布隆过滤器)

作者: 数大招疯 | 来源:发表于2018-02-25 17:55 被阅读0次

            背景:在翻阅吴军博士《数学之美》的时候看到布隆过滤器,所以在此总结下自己对其的认识。

    一、布隆过滤器用来做什么

            布隆过滤器可用来判定一个元素是否属于一个集合,更严谨的讲是:它能100%确定一个元素不属于某个集合,但不能100%确定一个元素属于某个集合。
            关于其使用场景,第一想到的是用来判定“是否需要执行高昂的操作”,比如访问网络或者磁盘上的某些资源。比如Google 的BitTable 和Apach HBase都使用布隆过滤器判断查询的数据是否存,来确定是否需要继续读取磁盘。再比如,用爬虫抓取网页时,有些网页会相互链接或者多个网页含有同一网页链接,所以使用布隆过滤器判断url是否爬取过了,来确定是否继续发起该url的访问。

    二、布隆过滤器是怎么实现和使用的

            布隆过滤器由两个部分组成:一个位数组和一组散列函数。为了初始化布隆过滤器,我们将位数组中的所有位设置为零。 所以,如果我们有一个十位数组:

    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    

            当为集合增加一个元素时,我们将元素作为输入提供给散列函数。 每个散列函数将输出一个数组索引。 假设将字符串“hello”传递给两个散列函数f1,f2,这两个散列函数给出索引0和4,我们将位数组中的相应位设置为1:

    [1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
    

            当查询一个元素时,我们将元素传给两个散列函数,获得两个索引后,检查数组中相应位的值:

    • 如果两个值中有0,可能的索引值组合有(0,0)、(0,1)、(1,0),即可判定该元素不在集合中。所以,不一定需要检查所有函数返回位的值,如果发现至少有一个值是0,那么即可判定该元素不在集合中。比如我们要查询“word”是否属于集合,假设两个函数返回的索引是1和5。因为两个索引位值都是0,所以检查其中任意一个位都可以得出“word不属于集合“的结论。
    • 如果两个值都是1,只可判定为“该元素可能在集合中”,因为散列函数可能会产生冲突。比如我们使用两个函数获取“bloom”的索引可能为1和9,获取“filter”的索引可能为5和7,而此时再去查询“word”,会因为1和9已被“bloom”和“filter”已经设置为1而产出冲突。因此,我们不能100%确定查询的元素在集合中。

            当去除一个元素集合时,因为“散列函数可能产生冲突”的问题,如果我们要重置希望删除元素的相应位,可能会误删具有相同索引位的其他元素,所以此时不需要(不容易)对位数组进行处理。

    三、为什么布隆过滤器效率比较高

    时间复杂度
    • 添加元素时,由于不需要迭代位数组,而是简单的设置索引位的值,所以操作所花费的时间仅取决于散列函数的个数,所以对于对于k个哈希函数的布隆过滤器,添加元素的时间复杂度为O(k) 。
    • 查询元素时,对于k个哈希函数的布隆过滤器,只需要在位数组中检查的索引数量有一个不变的上界,所以查询元素的时间复杂度也为O(k)。
    空间复杂度

            由于不需要存储元素,只需依赖一定长度的位数组判断是否存在,并且数组长度的大小不也取决于集合中元素的多少,可以在误判率变大或效率变低的代价下减少存储(位数组)。

    四、布隆过滤器有哪些缺点

            主要缺点是有一定的误判率和删除比较困难,所以随着存入集合的元素的增加,误判率也随之增加。误判率大小和三个指标有关:位数组长度m、集合长度n、散列函数个数k,其之间关系可以参考文献 ,该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时误判率是最小的。

    相关文章

      网友评论

        本文标题:简单、高效的数据结构--Bloom Filter(布隆过滤器)

        本文链接:https://www.haomeiwen.com/subject/tmwrxftx.html