使用Java手动实现布隆过滤器

（1）定义：布隆过滤器是一种来检索元素是否在给定大集合中的数据结构，这种数据结构优点是高效性能好，缺点是一定的错误识别率和删除难度。理论情况下，添加到集合中的元素越多，误报的可能性就越大。
（2）原理：布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。
（3）使用场景：判断元素存在于一个非常庞大的数据集中、防止缓存穿透、垃圾邮箱过滤、黑名单、爬虫URL去重等。
以上描述源自 JavaGuide.
手动实现如下：

import java.util.BitSet;
import java.util.Objects;

/** * 手动实现一个布隆过滤器，我们需要： * 1. 一个大小合适的位数组保存数据 * 2. 几个不同的哈希函数 * 3. 添加元素到位数组（布隆过滤器）的方法实现 * 4. 判断给定元素是否存在于位数组（布隆过滤器）的方法实现 * * @author roger * @create 2021-06-28 15:12 */
public class MyBloomFilter {
   
    /* * 位数组的大小 * */
    public static final int DEFAULT_SIZE = 2 << 24;
    /* * 通过这个数组可以创建6个不同的哈希函数 * */
    public static final int[] SEEDS = new int[] {
   3, 13, 46, 71, 91, 134};
    /* * 位数组，数组中的元素只能是0或者1 * */
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    /* * 存放包含hash函数的类的数组 * */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];
    /* * 初始化多个包含hash函数的类的数组，每个类中的hash函数都不一样 * */
    public MyBloomFilter() {
   
        // 初始化多个不同的Hash函数
        for (int i = 0; i < SEEDS.length; i++) {
   
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }
    /* * 添加元素到位数组 * */
    public void add(Object value) {
   
        for (SimpleHash f : func) {
   
            bits.set(f.hash(value), true);
        }
    }
    /* * 判断指定元素是否存在于为位数组 * */
    public boolean contains(Object value) {
   
        boolean ret = true;
        for (SimpleHash f : func) {
   
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /* * 静态内部类，用于hash操作！*/
    public static class SimpleHash {
   
        private int cap;
        private int seed;

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

        /* * 计算hash值 * */
        public int hash(Object value) {
   
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }

    public static void main(String[] args) {
   
// String value1 = "https://javaguide.cn/";
// String value2 = "https://github.com/Snailclimb";
// MyBloomFilter filter = new MyBloomFilter();
// System.out.println(filter.contains(value1));
// System.out.println(filter.contains(value2));
// filter.add(value1);
// filter.add(value2);
// System.out.println(filter.contains(value1));
// System.out.println(filter.contains(value2));
        Integer value1 = 13423;
        Integer value2 = 13423;
        MyBloomFilter filter = new MyBloomFilter();
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));
        filter.add(value1);
        filter.add(value2);
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));

    }
}