用java实现一个布隆过滤器

布隆过滤器是一种空间效率非常高的随机数据结构，用于快速检索一个元素是否在一个集合中。它有可能会误判，但不会漏判。

Java实现布隆过滤器需要用到以下几个类：

1. BitSet类：Java提供的一个位集合类，用于表示一个由0和1组成的序列。

2. Hash函数：布隆过滤器需要用到多个不同的Hash函数，用于将元素映射到不同的位上。在Java中可以使用MessageDigest类中的MD5、SHA等Hash函数。

下面是一个简单的Java实现布隆过滤器的代码：

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

public class BloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24; // 布隆过滤器的默认大小
    private static final int[] seeds = new int[]{7, 11, 13, 31, 37, 61}; // 随机种子，用于生成不同的Hash函数
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); // 初始化Hash函数
        }
    }

    // 将元素添加到布隆过滤器中
    public void add(String value) {
        if (value != null) {
            for (SimpleHash f : func) {
                bits.set(f.hash(value), true);
            }
        }
    }

    // 判断布隆过滤器是否包含指定元素
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        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;
        }

        public int hash(String value) {
            int result = 0;
            try {
                byte[] bytes = MessageDigest.getInstance("MD5").digest(value.getBytes());
                for (byte b : bytes) {
                    result += b;
                }
            } catch (NoSuchAlgorithmException e) {
                e.printStackTrace();
            }
            return (cap - 1) & (result * seed); // 生成Hash值
        }
    }

    public static void main(String[] args) {
        BloomFilter filter = new BloomFilter();
        filter.add("hello");
        filter.add("world");
        System.out.println(filter.contains("hello")); // true
        System.out.println(filter.contains("world")); // true
        System.out.println(filter.contains("java")); // false
    }
}

上面的代码中，我们使用了6个不同的随机种子，生成了6个不同的Hash函数。对于一个元素，我们使用每个Hash函数将其映射到6个不同的位上，然后将这6个位都设为1。当我们需要判断一个元素是否在布隆过滤器中时，我们使用每个Hash函数将其映射到6个不同的位上，然后判断这6个位是否都为1，如果都为1，则说明元素可能存在于布隆过滤器中，否则一定不存在于布隆过滤器中。

需要注意的是，布隆过滤器有可能会误判，即判断一个不存在的元素在布隆过滤器中存在。因此，在使用布隆过滤器时，需要根据实际情况来选择合适的参数，以控制误判率。