海量数据去重-由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日

相关推荐

  • leetcode590-N叉树的后序遍历

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

    2020年1月20日
    0100
  • leetcode123-买卖股票的最佳时机III

    原题 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你…

    算法 2020年6月16日
    01540
  • leetcode141-环形链表

    原题 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没…

    2019年12月14日
    0100
  • 剑指offer40-最小的k个数

    原题(来源Leetcode) 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。 示例 1: …

    算法 2020年3月20日
    0390
  • leetcode496-下一个更大元素I

    原题 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums…

    算法 2020年1月31日
    0410
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0470
  • leetcode313-超级丑数

    原题 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例: 输入: n = 12, primes = [2…

    算法 2020年2月11日
    0110
  • leetcode443-压缩字符串

    原题 给定一组字符,使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,…

    算法 2020年5月28日
    070
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0120
  • leetcode376-摆动序列

    原题 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,…

    算法 2020年2月18日
    0110

发表回复

登录后才能评论