布隆过滤器实现原理及源码解析

前⾔

布隆过滤器的作⽤是判断⼀个元素是否存在于⼀个集合中。

⽐如有⼀个集合存储了全国所有⼈的⾝份证号码，那么该集合⼤⼩有⼗⼏亿的⼤⼩，此时如果判断⼀个⾝份证是否存在于该集合中，最简单也是最笨的办法就是遍历集合，挨个判断是否和校验的⾝份证号码相同来判断。⽽布隆过滤器就是通过⼀个提⾼空间和时间效率的⼀种算法，来快速判断⼀个元素是否存在于集合中。

另外还有⼀个问题，如果采⽤遍历的⽅式，还有⼀个⽐较⼤的问题就是内存的问题，假设现有⼀个场景，有10亿个整数，需要判断⼀个整数是否存在于这个整数集合中。那么⾸先需要创建⼀个int类型的数组，int类型占⽤4个字节也就是32位，10亿个int类型占⽤的空间⼤⼩就是

4*1000000000/1024/1024/1024 = 3.72G，可以算出10亿个整数存在内存中⾄少就需要占⽤3.72个G的内存，如果是20亿，就是7个G的内存，很容易就会造成内存溢出了，所以⼤数据的情况下，通过遍历的⽅式显然是不⾏的。此时就可以通过bitmap来实现。

⼀、bitmap

bitmap也叫做位图，是⼀种数据结构。可以理解为是⼀个很长的数组，每⼀个数组元素是⼀个⼆进制值，⾮0即1，也就是说bitmap本质上是⼀个数组，每个数组元素是⼀个位的值。

如果通过bitmap来存在10亿个int类型，bitmap的⼤⼩为1000000000位/8/1024/1024 = 0.12G，可以发现通过为位图来表⽰10亿个整数值仅仅只需要120M⼤⼩的空间就可以表⽰，占⽤的内存⼤⼩⼤⼤减少。那么接下来就了解下bitmap的结构

1.1、bitmap的结构

int类型占⽤4个字节，1个字节占8位，也就是⼀个int类型占⽤32位，⽽bitmap是⼀位表⽰⼀个数字，所以可以容纳的数据是int类型的32倍。因为判断是否存在于⼀个集合中，只需要得到⼀个结果：在还是不在，那么就可以通过0和1来表⽰在还是不在。如下图：

上图中是⼀个int类型值在内存中的存储结构，⼀共占⽤了32位，每⼀位都对应了⼀个数字，对应的位置如果值为1，那么表⽰对应位置的值是存在的。如上图中可以分表表⽰ 2、9、12、27、31的值是存在的，⽽这整个32位对应⼀个int类型的数字。相当于⼀个int类型的值可以表⽰32个数字是否存在。

所以可以⽤⼀个int类型的数组来表⽰⼀个bitmap，每个int值可以代表32个bit值。

1.2、bitmap保存数据

将数字100保存到bitmap中，那么⾸先需要知道100需要存在int数组的那个位置，通过将 100/32=3可得到结果，则100位于int数字的第3个int值上知道了数组的那⼀位之后，接下来就需要设置当前数组位置上对应位的值。通过100%32=4可知位于int值的第4位，那么此时可以通过或运算进⾏设置将当前位置的int值和2的4次⽅的值进⾏或运算设置结果伪代码如下：

1 /** int数组表⽰bitmap */

2 static int[] bitmap = new int[]; 3

4 /**

5 * @param value:需要保存的值 6 * */

7 public static void putValue(int value){

8 /** 数组的每个int值可以保存32个数字, 通过除以32得到位于那个数组的位置 */ 9 int index = value/32;

10 /** 计算偏移位置,通过对32取余数得到位于int数字的具体位置 */11 int offset = value % 32;

12 /** 修改数组index位置的值,将当前的值和2的offset次⽅进⾏或运算*/13 bitmap[index] = bitmap[index] | (1<主要分成三步，第⼀步是计算数组的下标值，第⼆步是计算数组对应位置数字的第⼏位表⽰当前值，第三步是通过或运算修改当前数组位置上的值如现在需要判断10000个数字的bitmap，那么就需要创建10000/32长度的int数组。第⼀次向bitmap中插⼊数字35，那么步骤如下：

1、计算index值，35/32=1；那么对应的数值为bitmap[1]的数值，此时bitmap[1] = 0

2、计算偏移量，35%32=3；那么表⽰需要在bitmap[1]的数值的第3位设置为1，此时通过将当前的值和2的3次⽅进⾏或运算，如下：

0000 0000 0000 0000 0000 0000 0000 0000 | 0000 0000 0000 0000 0000 0000 0000 1000 = 8

3、此时bitmap[1]的值为8

4、再次向bitmap中插⼊数组40，index值为 40/32 = 1；同样对应bitmap[1]的值，此时bitmap[1] = 85、计算偏移量，40%32=8；那么需要将当前bitmap[1]的值和2的8次⽅进⾏或运算，如下：

0000 0000 0000 0000 0000 0000 0000 1000 | 0000 0000 0000 0000 0000 0001 0000 0000 = 0000 0000 0000 0000 0000 0001 0000 1000 = 2

6、此时bitmap[1]的值为2

同样的插⼊其他值的过程如出⼀辙。⽽删除的逻辑基本⼀致，第⼀步和第⼆步⼀模⼀样，第三步的话是通过和对应值进⾏取反操作并和当前值进⾏与运算即可，如从bitmap中删除40，过程如下：

/** 2的8次⽅为256,对于256进⾏取反操作,再和当前值进⾏与运算 */ bitmap[i] = bitmap[1] & (~ 256);

1.3、bitmap判断数据是否存在

判断数据是否存在的⽅式和存储的逻辑类似，⾸先第⼀步和第⼆步都是先的计算数组的下标值index和对应的位数偏移量offset

然后需要判断bitmap[index]的值对应的offset位置是否值为1即可，判断过程是将2的offset次⽅的值和bitmap[index]的值进⾏与运算，然后判断结果是否⼤于0，如果⼤于0则表⽰对应位的值就是1，否则就不是

如对上⾯的例⼦进⾏判断，⾸先依次插⼊35和40之后，分表对35和36进⾏判断是否存在于bitmap中，过程分别如下：

1、计算35对应的index值为1，偏移量offset值为3，那么2的3次⽅值为8，⼆进制为0000 0000 0000 0000 0000 0000 0000 10002、将8和当前数组对应位置的值bitmap[1]，也就是2，进⾏与运算，如下：

0000 0000 0000 0000 0000 0001 0000 1000 & 0000 0000 0000 0000 0000 0000 0000 1000 = 0000 0000 0000 0000 0000 0000 0000 1000 = 8

3、由于最后的结果8>0，所以得出结果为35存在于bitmap中

4、计算36对应的index值为1，偏移量offset值为4，那么2的4次⽅值为16，⼆进制为0000 0000 0000 0000 0000 0000 0001 00005、将16和当前数组对应位置的值bitmap[1]，也就是2，进⾏与运算，如下：

0000 0000 0000 0000 0000 0001 0000 1000 & 0000 0000 0000 0000 0000 0000 0001 0000 = 0000 0000 0000 0000 0000 0000 0000 0000 = 0

6、由于最后的结果为0，所以得出结果为37不存在于bitmap中

总结：

1、bitmap通过每⼀位表⽰⼀个整数来判断⼀个整数是否存在，所以应⽤场景就可以保护所有判断整数是否存在的场景。

2、bitmap同样会存在数据稀疏的问题，⽐如如果需要存在两个特别⼤的值，如存100个⼤于2的30次⽅的值，那么就需要分配相当⼤的存储空间，就会造成内存空间的浪费。所以bitmap仅仅适合数据量较⼤的情况下使⽤，对于集合数据量⼩的场景不实⽤3、bitmap仅仅只能⽤于整数的判断，⽆法判断字符串是否存在

⼆、布隆过滤器的实现

由上⼀节可知bitmap可以实现从⼀个⽐较⼤的整数集合中判断⼀个数字是否存在，但是实际场景中往往还会有其他的场景，⽐如从10亿个⾝份证判断某个⾝份证号码是否存在，很显然采⽤bitmap就⽆法实现了，因为bitmap只能判断整数是否存在。所以如果有⼀种⽅式能够将⾝份证号码的字符串转换成⼀个整数，那么就可以使⽤bitmap来实现判断字符串是否存在于⼀个集合中的需求了。⽽通过字符串转换成整数的⽅式也很普遍，那么就是采⽤hash函数通过计算字符串的hashCode来转换成整数。⽽布隆过滤器实际就是⼀系列的hash函数+bitmap实现的。

1、字符串存⼊bitmap中

布隆过滤器是通过bitmap实现的，只不过在bitmap之上添加了多个hash函数来对传⼊的数据转换正常整数类型。如下图⽰

字符串hello和字符串world，通过hash计算之后分别hashCode值为1和8，那么就可以通过bitmap的功能将1和8分别存⼊bitmap中，就相当于hello和world两个字符串存⼊了bitmap中。判断字符串是否存在时就可以通过计算hashCode的⽅式，判断对应的hash值是否存在于bitmap中即可可以判断字符串是否存在于bitmap中了

2、hash碰撞问题

虽然通过字符串计算hash值存⼊bitmap中表⾯上没有什么问题，但是hash函数是存在⼀定的碰撞概率的，也就是多个字符串计算出来的hash值是⼀样的，此时就会出现误判的情况。

如上图，判断字符串abcde是否存在，就需要先计算hashCode值，结果为8，此时判断结果为hashCode为8已经存在于bitmap中的，此时就会得到错误的判断是字符串abcde已经存在了，但是实际是并不存在的，⽽是出现了hashCode碰撞的情况。但是如果对应的hashCode在bitmap中不存在，那么就可以确认当前字符串不存在。⽽hashCode存在的情况下，只能说明当前字符串是可能存在。

所以你通过布隆过滤器只能实现的功能为：能够确认⼀个字符串不存在于集合中，但是⽆法确认⼀个字符串存在于集合中。

3、hash碰撞问题的优化

由于hash函数会存在hash碰撞的情况，就导致布隆过滤器的功能会出现⽐较⼤的误差，那么既然⼀个hash函数存在hash碰撞，就可以采⽤多个hash函数来降低hash碰撞的概率。⽐较不同的字符串通过多个不同的hash函数还碰撞的概率会⼤⼤降低。如下图：

字符串hello通过三个hash函数分别计算出来的hash值为1、8、25；字符串world通过三个hash函数计算出来的hash值为5、15、25，虽然hash值为25发⽣了hash碰撞的情况，但是两位两个hash值均没有发⽣hash碰撞，只有当通过三个hash函数计算出来的hash值都存在时才能够判断⼀个字符串可能存在，如果某个字符串通过三个hash函数计算出来的hash值只有部分存在，那么就是存在hash碰撞，且给字符串肯定不存在。

虽然通过多个hash函数可以对于误判的情况进⾏优化，但是并没有本质上解决误判的情况，因为毕竟从理论上还是可能会存在多个hash值发⽣了hash碰撞的情况的。⽐如⼀个字符串通过三个hash函数计算的值分别为1、5、15，那么虽然和上⾯两个字符串都不是全部冲突了，但是1和hello发⽣了冲突，5和15和world发⽣了冲突，如果hello和world都存在，那么就会导致hash值为1、5、15的字符串产⽣误判的情况。4、布隆过滤器删除元素

bitmap是⽀持删除元素的，因为bitmap不存在冲突的情况，每⼀个数字只会对应⼀个元素，⽽布隆过滤器的每⼀个元素都有可能会对应多个元素，所以不能通过删除的⽅式删除元素，因为这样可能会导致其他元素查询的结果不正确。

⽐如上图的例⼦，如果将world字符串删除，那么就需要将5、15、25三个位置的值置为0，此时再判断hello是否存在结果25的位置为0，那么就导致判断结果为hello字符串不存在了。

可以通过对每⼀位数字计算的⽅式判断每⼀位被hash冲突了多少次来实现删除元素的⽅式，但是每⼀位增加计算就会⼤⼤增加存储的空间。

总结：

布隆过滤器的本质是⼀个很长的位数组和⼀系列随机映射哈希函数

布隆过滤器判断存在的数据可能存在，布隆过滤器判断不存在的数据肯定不存在；

实际存在的数据布隆过滤器肯定判断存在，实际不存在的数据布隆过滤器可能会判断存在。

三、布隆过滤器的Java实现

google的guava包中提供了布隆过滤器的Java实现，对应的类为BloomFilter。使⽤案例如下：

1 public static void main(String[] args){ 2 int capacity = 100000;

3 /** 初始化容量为10万⼤⼩的字符串布隆过滤器,默认误差率为0.03

4 * 布隆过滤器容量为10万并⾮指bitmap的长度就是10万，因为需要考虑到存在hash冲突的情况，所以bitmap的实际长度要⽐10万要⼤很多 5 * bitmap长度⽐需要存在的数据量⼤⼩越⼤，误差率会越低 6 * */

7 BloomFilter bloomFilter =BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), capacity);

8

9 Set sets = new HashSet<>();10 List lists = new ArrayList<>();11

12 for (int i =0;i< capacity; i++){

13 String str = UUID.randomUUID().toString();14 bloomFilter.put(str);15 sets.add(str);16 lists.add(str);17 }18

19 int existsCount = 0;

20 int mightExistsCount = 0;21

22 for(int i=0;i<10000;i++){

23 //如果i为100倍数,取实际的值;否则就随机⼀个字符串

24 String data = i%100==0?lists.get(i/100):UUID.randomUUID().toString();25 /** 通过布隆过滤器判断字符串是否存在*/26 if(bloomFilter.mightContain(data)){

27 /** 如果布隆过滤器认为存在,则表⽰可能存在的数量mightExistsCount⾃增1*/28 mightExistsCount++;

29 /** 如果set中存在则existsCount⾃增1*/30 if(sets.contains(data)){31 existsCount++;32 }33 }34 }35

36 //测试总次数

37 BigDecimal total = new BigDecimal(10000);38 //错误总次数

39 BigDecimal error = new BigDecimal(mightExistsCount - existsCount);40 //误差率

41 BigDecimal rate = error.divide(total, 2, BigDecimal.ROUND_HALF_UP);42

43 System.out.println(\"初始化10万条数据,判断100个真实数据,9900个不存在数据\");44 System.out.println(\"实际存在的字符串个数为:\" + existsCount);

45 System.out.println(\"布隆过滤器认为存在的个数为:\" + mightExistsCount);46 System.out.println(\"误差率为:\" + rate.doubleValue());47 }

测试两次结果分别如下：

1 初始化10万条数据,判断100个真实数据,9900个不存在数据2 实际存在的字符串个数为:1003 布隆过滤器认为存在的个数为:4414 误差率为:0.03

1 初始化10万条数据,判断100个真实数据,9900个不存在数据2 实际存在的字符串个数为:1003 布隆过滤器认为存在的个数为:40 误差率为:0.03

在案例中通过BloomFilter类的静态⽅法create⽅法创建⼀个布隆过滤器，并初始化了需要存储数据的类型和数量，如案例中是存放String类型，并且容量为10万条数据。虽然容量是10万但是bitmap的实际长度远不⽌10万的长度，因为bitmap长度越⼤，hash碰撞导致的误差率就会越低。BloomFilter默认的误差率为0.03，也就是3%，可以通过初始化BloomFilter指定误差率。

案例中将10万条数据存⼊布隆过滤器，然后挑选100条真实存在的数据和9900条不存在的数据判断是否存在，结果显⽰为真实存在的100条，⽽布隆过滤器认为存在的数据条数为441条，也就是误差率为(441-100)/10000 = 0.03

同样误差率是可以调整的，但是不能调整为0，因为误差率为0从理论上是不可能的，只能通过扩⼤bitmap来尽量降低误差率。如上述案例设置误差率为0.01，那么初始化⽅法如下：

1 /** 指定误差率为0.01 */

2 BloomFilter bloomFilter =BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), capacity, 0.01);

继续测试上述案例，测试两次结果如下：

1 初始化10万条数据,判断100个真实数据,9900个不存在数据2 实际存在的字符串个数为:1003 布隆过滤器认为存在的个数为:18 误差率为:0.01

1 初始化10万条数据,判断100个真实数据,9900个不存在数据2 实际存在的字符串个数为:1003 布隆过滤器认为存在的个数为:2084 误差率为:0.01

可以看出虽然每次误差的数量不同，但是误差率都始终保持在了设定的范围之内。同样可以继续缩⼩误差率，⽐如将误差率分别设置为0.005和0.001，测试结果分别如下：

1 初始化10万条数据,判断100个真实数据,9900个不存在数据2 实际存在的字符串个数为:1003 布隆过滤器认为存在的个数为:1504 误差率为:0.005

1 初始化10万条数据,判断100个真实数据,9900个不存在数据2 实际存在的字符串个数为:1003 布隆过滤器认为存在的个数为:1114 误差率为:0.001

所以可以看出布隆过滤器只能控制误差率，但是永远也做不到没有误差，只能通过设置误差率尽量降低误差，但是永远不能设置为0，如果初始化设置为0那么会直接抛异常。另外误差率必须是⼩于1的值

四、布隆过滤器的源码简析

1、⾸先需要初始化布隆过滤器，通过BloomFilter的静态⽅法create⽅法创建，源码如下：

1 /**

2 * @param funnel:存⼊元素的类型

3 * @param expectedInsertions:期望保存元素的个数 4 * */

5 public static BloomFilter create(Funnel funnel, int expectedInsertions) { 6 //调⽤重载函数

7 return create(funnel, (long) expectedInsertions); 8 } 9

10 public static BloomFilter create(Funnel funnel, long expectedInsertions) {11 /** 默认误差率为0.03 */

12 return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions13 }14

15 /**

16 * @param fpp : 误差率17 * */

18 public static BloomFilter create(

19 Funnel funnel, long expectedInsertions, double fpp) {

20 return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_);21 }22

23 /**

24 * @param strategy : 哈希函数的策略25 * */

26 static BloomFilter create(

27 Funnel funnel, long expectedInsertions, double fpp, Strategy strategy) {28 //参数校验,误差率必须为⼤于0且⼩于129 checkNotNull(funnel);30 checkArgument(

31 expectedInsertions >= 0, \"Expected insertions (%s) must be >= 0\32 checkArgument(fpp > 0.0, \"False positive probability (%s) must be > 0.0\33 checkArgument(fpp < 1.0, \"False positive probability (%s) must be < 1.0\34 checkNotNull(strategy);35

36 /** 期待容量不可为0*/

37 if (expectedInsertions == 0) {38 expectedInsertions = 1;39 }40

41 /** 根据期待容量和误差率,计算bitmap的位数 */

42 long numBits = optimalNumOfBits(expectedInsertions, fpp);43 /** 根据期待容量和bitmap的位数,计算需要的hash函数的数量 */

44 int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);45 try {

46 /** 创建BloomFilter对象 */

47 return new BloomFilter(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);48 } catch (IllegalArgumentException e) {

49 throw new IllegalArgumentException(\"Could not create BloomFilter of \" + numBits + \" bits\50 }51 }

create⽅法重载⽐较多，主要都是在初始化参数，核⼼参数为需要保存元素的个数、误差率。然后通过容量和误差率计算bitmap需要的位数，并且计算需要经历多少次hash函数。2、向布隆过滤器中插⼊元素

BloomFilter插⼊元素调⽤了BloomFilter内部类Strategy的实现类的put⽅法，源码如下：

1 public boolean put(

2 T object, Funnel funnel, int numHashFunctions, LockFreeBitArray bits) { 3 /** bitmap长度 */

4 long bitSize = bits.bitSize();

5 long hash = Hashing.murmur3_128().hashObject(object, funnel).asLong(); 6 int hash1 = (int) hash;

7 int hash2 = (int) (hash >>> 32); 8

9 boolean bitsChanged = false;10 /** 遍历每个哈希函数 */

11 for (int i = 1; i <= numHashFunctions; i++) {12 int combinedHash = hash1 + (i * hash2);

13 // Flip all the bits if it's negative (guaranteed positive number)14 if (combinedHash < 0) {

15 combinedHash = ~combinedHash;16 }

17 /** 修改对应hash值上⾯的值 */

18 bitsChanged |= bits.set(combinedHash % bitSize);19 }

20 return bitsChanged;21 }

逻辑不复杂，就是通过计算出来的hash函数的个数，遍历执⾏多少次hash函数，修改bitmap上对应位置的值3、查询布隆过滤器是否存在元素

1 /** 判断元素是否可能存在,false则肯定不存在,true则表⽰可能存在 */ 2 public boolean mightContain(T object) {

3 return strategy.mightContain(object, funnel, numHashFunctions, bits); 4 } 5

6 public boolean mightContain(T object, Funnel funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) { 7 long bitSize = bits.bitSize();

8 long hash = Hashing.murmur3_128().hashObject(object, funnel).asLong(); 9 int hash1 = (int)hash;

10 int hash2 = (int)(hash >>> 32);11 /** 遍历执⾏多次hash函数 */

12 for(int i = 1; i <= numHashFunctions; ++i) {13 int combinedHash = hash1 + i * hash2;14 if (combinedHash < 0) {

15 combinedHash = ~combinedHash;16 }

17 /** 如果存在hash函数位不存在,直接返回false*/18 if (!bits.get((long)combinedHash % bitSize)) {19 return false;20 }21 }

22 /** 如果所有hash函数都命中,则返回true*/23 return true;24 }

五、布隆过滤器的应⽤

1、redis缓存穿透问题的解决，先将需要查询的数据存⼊布隆过滤器，如果布隆过滤器不存在则直接返回；如果布隆过滤器存在则再从redis查询（此时只会有少数误差数据）；如果redis中还不存在则查询数据库（此时的访问很⼩了），并在查询数据库可以通过并发加锁处理，保证只有⼀个线程可以查询该数据并写⼊缓存，从⽽避免了缓存穿透的问题2、爬给定⽹址的时候对已经爬取过的URL去重3、邮箱的垃圾邮件过滤、⿊名单等

4、经典⾯试题：⼀个10G⼤⼩的⽂件，存储内容为⾃然数，⼀⾏⼀个乱序排放，需要对其进⾏排序操作，但是机器的内存只有2G。

此时就可以通过布隆过滤器进⾏操作。⾸先将10G⼤⼩⽂件通过⼯具分隔成多个⼩⽂件，然后依次读取数据将数据存⼊bitmap中，10G的⼤⼩的⾃然数差不多可以存储27亿个左右的整数。

27亿个整数存⼊bitmap需要占⽤的空间为 2700000000/8/1024/1024 = 320M左右，所以内存是⾜够的。然后从1到最⼤值进⾏遍历判断是否存在于bitmap中从⽽达到排序的效果。