Redis 实现布隆过滤器

昨天听马士兵教育张福刚讲公开课，里面讲解了布隆过滤器，今天无聊没事干，整理了一下笔记。关于布隆过滤器是什么东西，有什么应用场景就不做讨论了，网上有很多，大家可以自行了解，只记录实现：

1. pom 依赖

<dependency>  
  <groupId>redis.clients</groupId>  
  <artifactId>jedis</artifactId>  
  <version>3.3.0</version>  
</dependency>

<dependency>  
  <groupId>com.google.guava</groupId>  
  <artifactId>guava</artifactId>  
  <version>18.0</version>  
</dependency>

2. 具体实现

package cn.bridgeli.demo;

import com.google.common.hash.Funnels;  
import com.google.common.hash.Hashing;  
import org.junit.Before;  
import org.junit.Test;  
import redis.clients.jedis.Jedis;  
import redis.clients.jedis.JedisPool;  
import redis.clients.jedis.Pipeline;

import java.nio.charset.StandardCharsets;

/**  
 * @author BridgeLi  
 * @date 2020/6/6 16:38  
 */  
public class BloomFilter {

  private Jedis jedis = null;

  /**  
   * 预估的数据量  
   */  
  static long n = 10000;

  /**  
   * 容忍的错误率  
   */  
  static double fpp = 0.01;

  private static long numBits = optimalNumOfBits(n, fpp);  
  private static int numHashFunctions = optimalNumOfHashFunctions(n, numBits);

  /**  
   * 根据预估数据量 n 和允许的错误率 fpp 计算需要的 bit 数组的长度  
   *  
   * @param n  
   * @param fpp  
   * @return  
   */  
  private static long optimalNumOfBits(long n, double fpp) {  
    if (0 == fpp) {  
      fpp = Double.MIN_VALUE;  
    }  
    return (long) (-n * Math.log(fpp) / (Math.log(2) * Math.log(2)));
  }

  /**  
   * 根据预估的数据量和计算出来的需要的 bit 数组的长度，计算所需要的 hash 函数的个数  
   *  
   * @param n  
   * @param numBits  
   * @return  
   */  
  private static int optimalNumOfHashFunctions(long n, long numBits) {  
    return Math.max(1, (int) Math.round((double) numBits / n * Math.log(2)));  
  }

  /**  
   * 预热数据  
   */  
  @Before  
  public void testBloomFilterBefore() {  
    BloomFilter bloomFilter = new BloomFilter();  
    bloomFilter.init();

    for (int i = 0; i < n; i++) {  
      bloomFilter.put("bf", String.valueOf(i + 100));  
    }  
  }

  /**  
   * 过滤数据  
   */  
  @Test  
  public void testBloomFilter() {   
    BloomFilter bloomFilter = new BloomFilter();  
    bloomFilter.init();

    int ex_count = 0;   
    int ne_count = 0;  
    for (int i = 0; i < 2 * n; i++) {  
      boolean exist = bloomFilter.isExist("bf", String.valueOf(i + 100));  
      if (exist) {  
        ex_count++;  
      } else {  
        ne_count++;  
      }  
    }

    System.out.println("ex_count: " + ex_count + ", ne_count: " + ne_count);  
  }

  private void init() {  
    JedisPool jedisPool = new JedisPool("127.0.0.1", 6379);  
    jedis = jedisPool.getResource();  
  }

  public boolean isExist(String where, String key) {  
    long[] indexs = getIndexs(key);

    boolean result = false;  
    try (Pipeline pipeline = jedis.pipelined()) {  
      for (long index : indexs) {  
        pipeline.getbit(where, index);  
      }  
      // 只要有一个位置为 false，即代表该数据不存在  
      result = !pipeline.syncAndReturnAll().contains(false);  
    } catch (Exception e) {

    }

    return result;  
  }

  public void put(String where, String key) {  
    long[] indexs = getIndexs(key);

    try (Pipeline pipeline = jedis.pipelined()) {  
      for (long index : indexs) {  
        pipeline.setbit(where, index, true);  
      }  
      pipeline.sync();  
    } catch (Exception e) {

    }

  }

  private long[] getIndexs(String key) {

    long hash1 = Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(StandardCharsets.UTF_8)).asLong();  
    long hash2 = hash1 >>> 16;

    long[] result = new long[numHashFunctions];

    for (int i = 0; i < numHashFunctions; i++) {  
      long combinedHash = hash1 + i * hash2;  
      if (combinedHash < 0) {  
        combinedHash = ~combinedHash;  
      }  
      result[i] = combinedHash % numBits;  
    }  
    return result;  
  }
}