布隆过滤器（Bloom Filter）：空间换时间的概率魔法

import java.util.BitSet;
import java.util.Random;

public class BloomFilter {
    private BitSet bitArray;
    private int size;
    private int[] hashSeeds; // 哈希函数种子
    private int hashCount;

    // 初始化：n=预期元素数量, p=可接受误判率
    public BloomFilter(int n, double p) {
        this.size = optimalSize(n, p);
        this.hashCount = optimalHashCount(n, size);
        this.bitArray = new BitSet(size);
        this.hashSeeds = new int[hashCount];
        Random rand = new Random();
        for (int i = 0; i < hashCount; i++) {
            hashSeeds[i] = rand.nextInt();
        }
    }

    // 添加元素
    public void add(String element) {
        for (int seed : hashSeeds) {
            int hash = (element.hashCode() ^ seed) % size;
            bitArray.set(Math.abs(hash), true);
        }
    }

    // 检查存在性
    public boolean contains(String element) {
        for (int seed : hashSeeds) {
            int hash = (element.hashCode() ^ seed) % size;
            if (!bitArray.get(Math.abs(hash))) return false;
        }
        return true; // 可能存在（有误判概率）
    }

    // 计算最优位数组大小（公式：m = -n*ln(p)/(ln2)^2）
    private int optimalSize(int n, double p) {
        return (int) (-n * Math.log(p) / (Math.pow(Math.log(2), 2)));
    }

    // 计算最优哈希函数数量（公式：k = m/n * ln2）
    private int optimalHashCount(int n, int m) {
        return Math.max(1, (int) (m / n * Math.log(2)));
    }

    public static void main(String[] args) {
        BloomFilter filter = new BloomFilter(1_000_000, 0.01);
        filter.add("user123");
        
        System.out.println(filter.contains("user123")); // true
        System.out.println(filter.contains("user456")); // false（可能误判）
    }
}

// 查询前先检查布隆过滤器
if (!bloomFilter.contains(key)) return null; // 避免查询数据库

if (!filter.contains(url)) {
    filter.add(url);
    crawl(url);
}

class CountingBloomFilter {
    private int[] countArray;
    public void remove(String element) {
        // 减少对应位的计数
    }
}