布隆过滤器原理以及java的实现


使用场景
布隆过滤器是可以用于判断一个元素是不是在一个集合内,以及大数据去重。
优点
布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数
缺点
布隆过滤器是有一定的误识别率以及删除困难的

算法思想
布隆过滤器算法主要思想就是利用k个哈希函数计算得到不同的哈希值,然后映射到相应的位数组的索引上,将相应的索引位上的值设置为1。判断该元素是否出现在集合中,就是利用k个不同的哈希函数计算哈希值,看哈希值对应相应索引位置上面的值是否是1,如果有1个不是1,说明该元素不存在在集合中。但是也有可能判断元素在集合中,但是元素不在,这个元素所有索引位置上面的1都是别的元素设置的,这就导致一定的误判几率。
布隆过滤的思想如下图所示:
布隆过滤器

java的简单实现

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class BloomFilter {

    private static final int DEFAULT_SIZE = Integer.MAX_VALUE;
    private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
    private static final BitSet bit = new BitSet(DEFAULT_SIZE);

    private static Hash[] hashes = new Hash[seeds.length];

    public BloomFilter() {
        System.out.println(DEFAULT_SIZE);
        for (int i = 0; i < hashes.length; i++) {
            hashes[i] = new Hash(seeds[i], DEFAULT_SIZE);
        }
    }

    public void add(String s) {
        for (int i = 0; i < hashes.length; i++) {
            bit.set(hashes[i].hash(s), true);
        }
    }

    public boolean contains(String s) {
        boolean ret = true;
        for (int i = 0; i < hashes.length; i++) {
            ret = bit.get(hashes[i].hash(s));
            if (!ret) {
                break;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 20000000; i++) {
            String val = "" + i;
            list.add(val);
            bloomFilter.add(val);
        }

        long s1 = System.currentTimeMillis();
        boolean b1 = list.contains("1000000s");
        long e1 = System.currentTimeMillis();
        System.out.println("是否存在1:" + b1 + " , 耗时:" + (e1 - s1));

        long s2 = System.currentTimeMillis();
        boolean b2 = bloomFilter.contains("1000000s");
        long e2 = System.currentTimeMillis();
        System.out.println("是否存在2:" + b2 + " , 耗时:" + (e2 - s2));

    }

    class Hash {

        private int seed;
        private int cap;

        public Hash(int seed, int cap) {
            this.seed = seed;
            this.cap = cap;
        }

        public int hash(String s) {
            int result = 0;
            for (int i = 0; i < s.length(); i++) {
                result = seed * result + s.charAt(i);
            }
            return (cap - 1) & result;
        }

    }

}

写文章

提问题

面试题