一、介绍

1.描述

标识阶段

1.定义一个位的数组

2.使用多个hash函数计算hash值并取模

3.将每个hash函数的取模的结果所对应的标志位置位1

过滤阶段

1.使用多个hash函数计算要查询数据的hash值并取模

2.在位数组中寻找，多个值对应的多个为是否全是1，如果有一个不是1就说明不存在该值

2.使用场景

解决缓存穿透问题、网页黑名单过滤、垃圾邮件过滤等

3.布隆过滤器的误差

因为布隆过滤器的自身特点，可能会存在误差。当布隆过滤器的返回值为false时（不存在），说明这个数据一定不存在，布隆过滤器中的值为true时，有不存在的可能，这就产生了误差。

但我们可以通过下面的公式规定布隆过滤器的大小 和 hash函数的个数  来设定误差在我们可以接受的范围中

布隆过滤器的大小m公式: 其中p是失误率  n是数据的数量

公式1：

如果我们的数据量是n=100亿，失误率p=0.01%，通过公式1就能够得到m的值 

哈希函数的个数k公式:                                      

通过公式1，得到了m的值，就可以进一步计算，hash函数的个数。

二、实现

1.关键词

几个自定义的hash函数

一个位数组：Java.util包的BitSet类 或者 redis的bitmap

2.Java 实现

（1）.通过bitset实现

import java.util.BitSet;public class BloomFilter {//bloomFilter大小private static final int SIZE = 1<<24;//bitset初始化private static final BitSet bitset=new BitSet();//    计算hash值的辅助数组static final int[] seeds= {2, 3, 5, 7, 11, 13, 17, 19};//获取hash值public static int getHash(String data,int seed){int hash = 0;char arrChar[] = data.toCharArray();if (arrChar.length>0){for (int i = 0;i<arrChar.length;i++){hash = hash*seed+arrChar[i];//自定义hash算法}}return hash&(SIZE-1);}//  过滤  查找是否存在public static boolean isExist(String data){if(data==null&&data.length()==0){return false;}boolean res = true;for (int i = 0;i<seeds.length;i++){int index = getHash(data,seeds[i]);res&=bitset.get(index);//与运算，只要有有一个位置为null就false}return res;}//    标识  bitset置位 public static void add(String data){for (int i = 0;i<seeds.length;i++){int  hash = getHash(data,seeds[i]);bitset.set(hash,true);}}public static void main(String[] args) {System.out.println(isExist("111111"));//falseadd("111111");System.out.println(isExist("111111"));//trueSystem.out.println(isExist("1111112"));//falseadd("1111112");System.out.println(isExist("1111112"));//true}
}

（2）.通过redis 的 bitmap来实现

我是在在自己之前的一个springBoot项目中实现的。但是其实只要是该项目能操作redis就可以实现。

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;import java.util.BitSet;@Service
public class BloomFilterRedisBitmap {@Autowiredprivate RedisTemplate redisTemplate;//bloomFilter大小private static final int SIZE = 1 << 24;// 计算hash值的辅助数组private static final BitSet bitset = new BitSet();// hash函数,一个数组static final int[] seeds = {2, 3, 5, 7, 11, 13, 17, 19};public int getHash(String data, int seed) {int hash = 0;char arrChar[] = data.toCharArray();if (arrChar.length > 0) {for (int i = 0; i < arrChar.length; i++) {hash = hash * seed + arrChar[i];//自定义hash算法}}return hash & (SIZE - 1);}//   过滤 isExistpublic boolean isExist(String data) {if (data == null && data.length() == 0) {return false;}boolean res = true;for (int i = 0; i < seeds.length; i++) {int index = getHash(data, seeds[i]);//通过与运算，判断多个index位是否为1，只要有一个位是0 res 就是falseres &= redisTemplate.opsForValue().getBit("hashKey", index);}return res;}//标识  置位public void add(String data) {for (int i = 0; i < seeds.length; i++) {int hash = getHash(data, seeds[i]);redisTemplate.opsForValue().setBit("hashKey", hash, true);}}
}

参考：

1.《程序员代码面试指南》左程云

2.https://www.cnblogs.com/zhenlingcn/p/8231786.html