本文参考资源：

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

概述

昨天学习了BitMap这种数据结构（算法），链接：海量数据算法-BitMap介绍和实现

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

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

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

当元素不是整型的时候，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功能较单一，无法根据已有的位倒推回原始数据，只能用作查询去重功能。

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

参数调优

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

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

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

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

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

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

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

应用

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

Redis4.0后开始以插件的形式支持布隆过滤器（安装后使用指令bf.add和bf.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/

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

概述

原理

参数调优

应用

发表回复

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

概述

原理

参数调优

应用

相关推荐

发表回复