布隆过滤器（Bloom Filter）

布隆过滤器（Bloom Filter）是一种空间有效的概率数据结构，用于判断一个元素是否在一个集合中。它具有很高的空间效率和查询速度，但是有一定的误报率。

布隆过滤器通常用于缓存系统、网络路由、广告系统等场景。

布隆过滤器的基本原理如下：

1. 初始化一个长度为m的位数组，所有位都设为0。
2. 选择k个独立的哈希函数，每个函数将输入映射到0到m-1的范围。
3. 添加元素时，用k个哈希函数计算出k个索引，将位数组中对应的位设为1。
4. 查询元素时，用k个哈希函数计算出k个索引，如果位数组中所有对应的位都是1，说明元素可能在集合中；如果有任何一个位是0，则元素一定不在集合中。
5. 删除元素时，布隆过滤器不能直接删除。可以考虑使用Counting Bloom Filter或Cuckoo Filter等替代方案。

注意：布隆过滤器存在误报率，即判断元素在集合中的情况实际上是不在集合中。误报率取决于位数组长度、哈希函数数量等参数。

以下是一个简单的Java实现：

import java.util.BitSet;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class BloomFilter {
    private final BitSet bitSet;
    private final int k; // Number of hash functions
    private final int m; // Size of the bit array

    public BloomFilter(int m, int k) {
        this.m = m;
        this.k = k;
        this.bitSet = new BitSet(m);
    }

    public void add(String value) {
        byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
        for (int i = 0; i < k; i++) {
            int index = Math.abs(hash(bytes, i)) % m;
            bitSet.set(index);
        }
    }

    public boolean contains(String value) {
        byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
        for (int i = 0; i < k; i++) {
            int index = Math.abs(hash(bytes, i)) % m;
            if (!bitSet.get(index)) {
                return false;
            }
        }
        return true;
    }

    private int hash(byte[] bytes, int seed) {
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            md.update((byte) seed);
            byte[] digest = md.digest(bytes);
            int hash = 0;
            for (int i = 0; i < 4; i++) {
                hash <<= 8;
                hash |= ((int) digest[i]) & 0xFF;
            }
            return hash;
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("SHA-256 not supported", e);
        }
    }
}

使用示例：

public static void main(String[] args) {
    BloomFilter bloomFilter = new BloomFilter(10000, 5);
    bloomFilter.add("example");
    bloomFilter.add("test");
    bloomFilter.add("hello");
    bloomFilter.add("world");

    System.out.println("Checking existence of elements:");
    System.out.println("example: " + bloomFilter.contains("example")); // should return true
    System.out.println("test: " + bloomFilter.contains("test")); // should return true
    System.out.println("hello: " + bloomFilter.contains("hello")); // should return true
    System.out.println("world: " + bloomFilter.contains("world")); // should return true
    System.out.println("unknown: " + bloomFilter.contains("unknown")); // should return false (but may return true due to false positives)
}

在这段完整的代码示例中，我们首先创建了一个容量为10000且哈希函数数量为5的BloomFilter实例。然后，将四个字符串（"example"，"test"，"hello"和"world"）添加到布隆过滤器中。接下来，我们检查这四个字符串以及一个不存在的字符串（"unknown"）是否包含在布隆过滤器中。

由于布隆过滤器可能存在误报，因此当检查"unknown"字符串时，它可能返回true。然而，在实际应用中，布隆过滤器的误报率通常可以通过调整容量和哈希函数数量来控制在一个可接受的范围内。