海量数据去重-由BitMap引出的布隆过滤器

布隆过滤器(图文无关)

本文参考资源:

那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客

详解布隆过滤器的原理、使用场景和注意事项 - 简书

概述

昨天学习了BitMap这种数据结构(算法),链接:海量数据算法-BitMap介绍和实现

然而BitMap也存在着一些问题:

  1. 当样本分布极度不均匀的时候,BitMap会造成很大空间上的浪费。

举个例子,比如你有10个数,分别是1、2、3、4、5、6、7、8、99999999999;那么你不得不用99999999999个bit位去实现你的BitMap,而这个BitMap的中间绝大多数位置都是0,并且永远不会用到,这显然是极度不划算的。

  1. 当元素不是整型的时候,BitMap就不适用了。
    想想看,你拿到的是一堆url,然后如果你想用BitMap做去重的话,先得把url转换成int型,在转换的过程中难免某些url会计算出相同的int值,于是BitMap的准确性就会降低。

那针对这两种情况有没有解决办法呢?

第一种分布不均匀的情况可以通过hash函数,将元素都映射到一个区间范围内,减少大段区间闲置造成的浪费,这很简单,取模就好了,难的是取模之后的值保证不相同,即不发生hash冲突。

第二种情况,把字符串映射成整数是必要的,那么唯一要做的就是保证我们的hash函数尽可能的减少hash冲突,一次不行我就多hash几次,hash还是容易碰撞,那我就扩大数组的范围,使hash值尽可能的均匀分布,减少hash冲突的概率。

基于这种思想,BloomFilter(布隆过滤器)诞生了。

原理

比如现在有10000个字符串,要进行去重操作,如果用bitmap的方法将字符串的哈希值对应到一个bit,由于字符串的哈希值不是唯一的,可能出现哈希冲突,而若两个字符串哈希冲突了,就会对应到同一个bit上,bitmap就会误判这两个字符串相等。

解决的方法就是,使用多个哈希函数,例如使用三个哈希函数,每个字符串可以计算出三个哈希映射,将所有映射的位标为1,而判断有没有重复的方法是,只要得到的三个映射位不是都已为1了,就认为该字符串没有重复。

海量数据去重-由BitMap引出的布隆过滤器

海量数据去重-由BitMap引出的布隆过滤器

可见布隆过滤器相较于BitMap功能较单一,无法根据已有的位倒推回原始数据,只能用作查询去重功能。

但这也不意味着布隆过滤器就不会误判,假如一个新的无重复的字符串,映射的位在之前就被其他字符串得到的哈希映射都标为了1,那么布隆过滤器也认为它是重复的。不过误判的概率较小(比BitMap小多了),在大部分生产环境下是可以接受的(因为有的时候不重复的字符串没多少,反而重复的字符串占了大多数,主要目的只是不用反复处理重复的字符串)。

参数调优

由上面的原理可知,对于布隆过滤器性能最重要的参数有两个:

  • bit数组的大小,bit越多且哈希映射分布均匀的条件下,哈希冲突的概率是越低的。
  • 哈希函数的个数,哈希函数的个数如果太少,更容易冲突,而如果哈希函数的个数太多,则将bit数组内的元素标为1的进度也会加快,从而造成哈希冲突。所以哈希函数的个数需要均衡。

误判率和数组bit个数的关系

关于具体的误判率计算维基百科给出了计算过程:Bloom filter - Wikipedia

对于一个期望的误判率p,期望的插入元素个数n,最佳数组bit个数m和哈希函数数量k的计算公式如下:

最佳数组bit个数

最佳哈希函数数量

所以当构造一个布隆过滤器的时候并且希望误判率可控时通常要传入期望的误判率、期望的插入元素个数等参数。

谷歌有java中BloomFilter的实现,有兴趣的可以自己去研究一下:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>25.1-jre</version>
</dependency>

应用

  • 重复URL的过滤
  • 邮箱黑名单的去重
  • 推荐去重

Redis4.0后开始以插件的形式支持布隆过滤器(安装后使用指令bf.addbf.exist

Redis防止缓存穿透就可以使用布隆过滤器,日后再谈。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e6%b5%b7%e9%87%8f%e6%95%b0%e6%8d%ae%e5%8e%bb%e9%87%8d-%e7%94%b1bitmap%e5%bc%95%e5%87%ba%e7%9a%84%e5%b8%83%e9%9a%86%e8%bf%87%e6%bb%a4%e5%99%a8/

(3)
彭晨涛彭晨涛管理者
上一篇 2020年2月28日
下一篇 2020年2月28日

相关推荐

  • AVL树-自平衡的二叉搜索树

    本文图片来源:手把手教,手写AVL树 - 不止是编程 - 博客园 AVL树的概念 自平衡 当二叉搜索树处于平衡状态的时候,其操作时间复杂度为O(logN),但当二叉搜索树是单支树的…

    2019年11月25日
    0420
  • leetcode589-N叉树的前序遍历

    原题 给定一个 N 叉树,返回其节点值的前序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [1,3,5,6,2,4]。 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月19日
    01010
  • 程序员面试金典01.06-字符串压缩

    原题(来源Leetcode) 字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字…

    算法 2020年3月16日
    0230
  • leetcode83-删除排序链表中的重复元素

    今天打算多刷几道算法题 原题 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->…

    算法 2020年6月16日
    01330
  • leetcode2-两数相加

    原题 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回…

    算法 2019年12月17日
    080
  • leetcode26-删除排序数组中的重复项

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空…

    算法 2019年11月23日
    0190
  • leetcode25-K个一组翻转链表

    原题 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原…

    算法 2020年5月9日
    0540
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04570
  • leetcode24-两两交换链表中的节点

    原题 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例: 给定 1->2->3->…

    算法 2020年1月20日
    0200
  • leetcode374-猜数字大小

    原题 我们正在玩一个猜数字游戏。 游戏规则如下:我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了,我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接…

    算法 2019年12月31日
    0370

发表回复

登录后才能评论