为了高效的插入数据和查询数据
现实场景：从上亿数据中判断一条数据是否存在，使用map，set等常规数据结构，导致内存急速膨胀，需要大量空间，需要一种更为巧妙的方式，判断数据是否存在，常见的缓存击穿的问题
1,底层由一个bit数组构成，更改bit数组有多个hash函数完成
bit数组中由0，1构成，当有一个数据进来时，通过3个不同的hash函数，将其映射在不同的位置，值设定为1
例如：baidu被映射到1，4，7位置
其他数据进来时也会映射到不同的位置，但由于hash函数和数组长度问题，总会有数据的映射位与其他数据的映射位冲突
所以：
#从容器的角度来说： 如果布隆过滤器判断元素在集合中存在，不一定存在 如果布隆过滤器判断不存在，一定不存在 #从元素的角度来说： 如果元素实际存在，布隆过滤器一定判断存在 如果元素实际不存在，布隆过滤器可能判断存在 #布隆过滤器会导致一定的误判行为并不是单独的数据结构，而是由字符串类型（底层实现sds）之上定义比特相关的操作实现的，此时sds被当成位数组了，可以去单独对位进行操作，但字符串还是字符串，只是有着这样的操作
例如:
#因为是字符串，所以数组的最大长度为512M，所以多达2^32个位置可以进行设置 #常用命令： GETBIT只是返回指定索引处的位的值。超出范围的位（寻址超出存储在目标键中的字符串长度的位）始终被视为零。 在位组上有三个命令： BITOP在不同的字符串之间执行按位运算。提供的运算为AND，OR，XOR和NOT。 BITCOUNT执行填充计数，报告设置为1的位数。 BITPOS查找指定值为0或1的第一位。2.编写bloomHelp类
* 布隆过滤器 * * * 算法过程： * 1，首先函数需要K个hash函数，将一个数据映射到bit数组的k个位置 * 2，初始时需要知道bit数组大小，默认为0 * 3，某一个key加入集合时，判断大小，算出bit数组大小，进而得出hash函数执行次数 * 4，返回一个k长度大小的数组，表示在bit数组中这些位置的值为1 * */ public class BloomFilterHepler<T> { private int numHashFunctions; private int bitSize; private Funnel<T> funnel; public BloomFilterHepler(Funnel<T> funnel, int expectedInsertions, double fpp) { this.funnel = funnel; // 计算bit数组长度 bitSize = optimalNumOfBits(expectedInsertions, fpp); // 计算hash方法执行次数 numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize); } public int[] RedisHashFunction(T value) { int bit[]=new int[numHashFunctions]; long hash64 = Hashing.murmur3_128().hashObject(value,funnel).asLong(); int hash1=(int)hash64; int hash2=(int)hash64>>>32; for(int i=1;i<=numHashFunctions;i++) { int nextHash=hash1+i*hash2; if(nextHash<0) { nextHash=~nextHash; } bit[i-1]=nextHash%bitSize; } return bit; } /** * 计算bit数组长度 */ private int optimalNumOfBits(long n, double p) { if (p == 0) { // 设定最小期望长度 p = Double.MIN_VALUE; } int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); return sizeOfBitArray; } /** * 计算hash方法执行次数 */ private int optimalNumOfHashFunctions(long n, long m) { int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2))); return countOfHash; } }3.编写redis操作类
public class RedisServer<T> { @Autowired private RedisTemplate redisTemplate; //根据value值放入布隆过滤器中 public Object addBoolmKeys(BloomFilterHepler<T> bloomFilterHepler, String key, T value) { int bit[] = bloomFilterHepler.RedisHashFunction(value); for (int i : bit) { System.out.println("bit i:" + i); redisTemplate.opsForValue().setBit(key, i, true); } return null; } public Object addBoolmKeysList(BloomFilterHepler<T> bloomFilterHepler, String key, List<T> value) { for (T v : value) { int bit[] = bloomFilterHepler.RedisHashFunction(v); for (int i : bit) { System.out.println("bit i:" + i); boolean result=redisTemplate.opsForValue().setBit(key, i, true); System.out.println("result:"+result); } } return null; } //根据同样的传入值得到同样的bit数组，然后判断bit位是否为1 public boolean getBoolmKeys(BloomFilterHepler<T> bloomFilterHepler, String key, T value) { int bit[] = bloomFilterHepler.RedisHashFunction(value); for (int i : bit) { System.out.println("bit i:" + i); if (!redisTemplate.opsForValue().getBit(key, i)) { return false; } } return true; } }4.测试类
@Resource private RedisServer redisServer; @GetMapping("/addbloom") public String addbloom() { int expectNums = 1000; double fpp = 0.02; BloomFilterHepler bloomFilterHepler = new BloomFilterHepler(Funnels.stringFunnel(Charset.defaultCharset()), expectNums, fpp); List<String> list = new ArrayList<>(); for (int i = 0; i < 1000; i++) { list.add(i + ""); } redisServer.addBoolmKeysList(bloomFilterHepler, "bloom", list); int j = 0; for (int i = 0; i < 100; i++) { boolean result = redisServer.getBoolmKeys(bloomFilterHepler, "bloom", i + ""); if (!result) { j++; } } return "漏掉了{" + j + "}个"; }布隆过滤通过位图bitmap的为操作，将一个key通过多次hash算法，在位图上有不同的映射位，从而能够实现插入；当要查询是否存在时，将同样的key值再次进行多次hash计算，得到位图映射位置，如果都是1，表明可能存在。
不过判断有误判。
