吊打面试官：海量数据处理利器,布隆过滤器

public class MyBloomFilter {
    /**
     * 一个长度为10 亿的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;
    /**
     * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
    /**
     * 相当于构建 8 个不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];
    /**
     * 初始化布隆过滤器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);
    /**
     * 添加数据
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //计算 hash 值并修改 bitmap 中相应位置为 true
                bitset.set(f.hash(value), true);
            }
        }
    }
    /**
     * 判断相应元素是否存在
     * @param value 需要判断的元素
     * @return 结果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一个 hash 函数返回 false 则跳出循环
            if (!ret) {
                break;
            }
        }
        return ret;
    }
    /**
     * 模拟用户在不在线。。。
     */
    public static void main(String[] args) {
        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }
        // 添加1亿数据
        for (int i = 0; i < 100000000; i++) {
            add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);
        System.out.println(contains(id));   //结果： true
        System.out.println("" + contains("234567890"));  //结果： false
    }
}
class HashFunction {
    private int size;
    private int seed;
    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }
    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }
}

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

// 创建布隆过滤器对象，预计包含的数据量：2000个，和允许的误差值0.01
BloomFilter<Integer> filter = BloomFilter.create(
        Funnels.integerFunnel(),
        2000,
        0.01);
System.out.println(filter.mightContain(10));// 判断指定元素是否存在
System.out.println(filter.mightContain(20));
filter.put(10);// 将元素添加进布隆过滤器
filter.put(20);
System.out.println(filter.mightContain(10));// 判断指定元素是否存在
System.out.println(filter.mightContain(20));

~ docker pull redislabs/rebloom:latest
~ docker run -p 6379:6379 --name redis-bloom redislabs/rebloom:latest
~ docker exec -it redis-bloom bash 
root@113d012d35:/data# redis-cli
127.0.0.1:6379> 

//-------------------------常用命令
BF.ADD --添加一个元素到布隆过滤器
BF.EXISTS --判断元素是否在布隆过滤器
BF.MADD --添加多个元素到布隆过滤器
BF.MEXISTS --判断多个元素是否在布隆过滤器
//-------------------------具体操作
127.0.0.1:6379> BF.ADD myFilter hello
(integer) 1
127.0.0.1:6379> BF.ADD myFilter people
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter hello
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter people
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0