布隆过滤器

算法定义

布隆过滤器是一种空间高效的概率性数据结构，用于判断一个元素是否属于某个集合。它的核心特点是：

能高效地判断 "元素一定不存在" 或 "元素可能存在"
存在一定的误判率（False Positive，即错误地认为不存在的元素存在）
不会出现漏判（False Negative，即不会认为存在的元素不存在）

布隆过滤器由位数组（BitSet） 和多个哈希函数组成，通过哈希函数将元素映射到位数组的多个位置，实现高效的存在性判断。

算法思路

布隆过滤器的核心操作包括：

初始化：
- 创建一个长度为m的位数组，初始所有位均为 0
- 选择k个独立的哈希函数
插入元素：
- 对于元素x，使用k个哈希函数计算得到k个哈希值
- 将位数组中对应这k个哈希值的位置设为 1
查询元素：
- 对于待查询元素x，使用k个哈希函数计算得到k个哈希值
- 检查位数组中这些位置是否全为 1：
  - 若有任何一位为 0，则元素一定不存在于集合中
  - 若所有位均为 1，则元素可能存在于集合中（存在误判可能）
删除元素：
- 标准布隆过滤器不支持删除操作（因多个元素可能共享位，删除会影响其他元素）

算法复杂度

插入操作：O(k)，k为哈希函数数量，与数据规模无关
查询操作：O (k)，同样仅与哈希函数数量有关
最坏 / 平均时间复杂度：均为 O (k)，哈希函数计算为常数时间
空间复杂度：O(m)，m为位数组长度，远小于集合中元素的实际存储大小

误判率公式（近似）： P ≈ (1 - e^(-kn/m))^k 其中n为插入的元素数量，k为哈希函数数量，m为位数组长度。通过调整k和m可控制误判率。

优点与缺点

优点：
- 空间效率极高，存储成本远低于哈希表（通常只需几个字节 / 元素）
- 插入和查询速度快，时间复杂度为 O (k)
- 支持海量数据场景，可处理远超内存容量的数据
- 不存储原始数据，具有一定的隐私保护特性
缺点：
- 存在误判率（False Positive），无法 100% 准确
- 标准实现不支持删除操作
- 哈希函数选择对性能和误判率影响大
- 元素数量接近或超过设计容量时，误判率会急剧上升

应用场景

缓存穿透防护：数据库查询前先通过布隆过滤器判断 ID 是否存在，避免对不存在的 ID 进行无效查询
分布式系统中的重复判断：如分布式爬虫的 URL 去重
垃圾邮件过滤：判断邮件地址是否在黑名单中
集合成员快速判断：如判断一个用户名是否已被注册
大规模数据去重：如日志分析中过滤重复记录
LevelDB/RocksDB 等存储引擎：用于快速判断键是否存在

Java 实现及优化版本

import java.util.BitSet;
import java.util.Random;
import java.util.function.Function;
import java.util.List;
import java.util.ArrayList;

public class Main {

    // 1. 基础布隆过滤器实现
    static class BasicBloomFilter {
        private final BitSet bitSet;      // 位数组
        private final int bitSetSize;     // 位数组大小
        private final int hashFunctionCount;  // 哈希函数数量
        private final Function<String, Integer>[] hashFunctions;  // 哈希函数数组

        // 构造函数：指定预期元素数、可接受的误判率
        public BasicBloomFilter(int expectedElements, double falsePositiveRate) {
            // 计算最优位数组大小 m = -n * ln(p) / (ln(2))^2
            this.bitSetSize = (int) (-expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2)));
            // 计算最优哈希函数数量 k = m/n * ln(2)
            this.hashFunctionCount = (int) (this.bitSetSize * Math.log(2) / expectedElements);
            
            this.bitSet = new BitSet(bitSetSize);
            this.hashFunctions = createHashFunctions(hashFunctionCount, bitSetSize);
        }

        // 创建多个不同的哈希函数
        @SuppressWarnings("unchecked")
        private Function<String, Integer>[] createHashFunctions(int count, int mod) {
            Function<String, Integer>[] functions = new Function[count];
            Random random = new Random(42);  // 固定种子保证一致性
            
            for (int i = 0; i < count; i++) {
                int salt = random.nextInt();  // 每个哈希函数使用不同的盐值
                functions[i] = s -> {
                    int hash = s.hashCode() ^ salt;  // 结合盐值的哈希计算
                    return Math.abs(hash % mod);     // 映射到位数组范围
                };
            }
            return functions;
        }

        // 插入元素
        public void add(String element) {
            for (Function<String, Integer> hashFunc : hashFunctions) {
                int position = hashFunc.apply(element);
                bitSet.set(position);
            }
        }

        // 判断元素是否可能存在
        public boolean mightContain(String element) {
            for (Function<String, Integer> hashFunc : hashFunctions) {
                int position = hashFunc.apply(element);
                if (!bitSet.get(position)) {
                    return false;  // 有一位为0，一定不存在
                }
            }
            return true;  // 所有位为1，可能存在
        }

        // 获取当前误判率估计
        public double estimateFalsePositiveRate(int actualElements) {
            // 公式：(1 - e^(-kn/m))^k
            double p = Math.pow(1 - Math.exp(-(double) hashFunctionCount * actualElements / bitSetSize), hashFunctionCount);
            return p;
        }
    }

    // 2. 优化版1：支持动态扩容的布隆过滤器
    static class ScalableBloomFilter {
        private final double falsePositiveRate;  // 初始误判率
        private final double scaleFactor;        // 扩容因子（通常为2）
        private List<BasicBloomFilter> filters;  // 过滤器列表
        private int expectedElements;            // 预期元素数

        public ScalableBloomFilter(int initialExpectedElements, double falsePositiveRate) {
            this.expectedElements = initialExpectedElements;
            this.falsePositiveRate = falsePositiveRate;
            this.scaleFactor = 2.0;
            this.filters = new ArrayList<BasicBloomFilter>();
            // 添加第一个过滤器
            this.filters.add(new BasicBloomFilter(initialExpectedElements, falsePositiveRate));
        }

        public void add(String element) {
            // 检查是否需要扩容（最后一个过滤器元素数接近预期）
            BasicBloomFilter lastFilter = filters.get(filters.size() - 1);
            if (estimateElementCount(lastFilter) >= expectedElements) {
                // 扩容：创建更大的过滤器，误判率更低
                expectedElements = (int) (expectedElements * scaleFactor);
                double newFpr = falsePositiveRate / Math.pow(scaleFactor, filters.size());
                filters.add(new BasicBloomFilter(expectedElements, newFpr));
                lastFilter = filters.get(filters.size() - 1);
            }
            lastFilter.add(element);
        }

        public boolean mightContain(String element) {
            // 检查所有过滤器
            for (BasicBloomFilter filter : filters) {
                if (filter.mightContain(element)) {
                    return true;
                }
            }
            return false;
        }

        // 估计过滤器中的元素数量
        private int estimateElementCount(BasicBloomFilter filter) {
            // 基于位数组中1的比例估算：n ≈ -m/k * ln(1 - bitsSet/m)
            int bitsSet = filter.bitSet.cardinality();
            double ratio = (double) bitsSet / filter.bitSetSize;
            return (int) (-filter.bitSetSize * Math.log(1 - ratio) / filter.hashFunctionCount);
        }
    }

    // 3. 优化版2：支持删除操作的计数布隆过滤器
    static class CountingBloomFilter {
        private final int[] countArray;    // 计数数组（替代位数组）
        private final int bitSetSize;
        private final int hashFunctionCount;
        private final Function<String, Integer>[] hashFunctions;
        private final int maxCount;        // 最大计数值（防止溢出）

        public CountingBloomFilter(int expectedElements, double falsePositiveRate, int maxCount) {
            this.bitSetSize = (int) (-expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2)));
            this.hashFunctionCount = (int) (this.bitSetSize * Math.log(2) / expectedElements);
            this.countArray = new int[bitSetSize];
            this.maxCount = maxCount;
            this.hashFunctions = createHashFunctions(hashFunctionCount, bitSetSize);
        }

        @SuppressWarnings("unchecked")
        private Function<String, Integer>[] createHashFunctions(int count, int mod) {
            // 与基础版相同的哈希函数创建逻辑
            Function<String, Integer>[] functions = new Function[count];
            Random random = new Random(42);
            for (int i = 0; i < count; i++) {
                int salt = random.nextInt();
                functions[i] = s -> Math.abs((s.hashCode() ^ salt) % mod);
            }
            return functions;
        }

        public void add(String element) {
            for (Function<String, Integer> hashFunc : hashFunctions) {
                int position = hashFunc.apply(element);
                if (countArray[position] < maxCount) {
                    countArray[position]++;
                }
            }
        }

        public boolean mightContain(String element) {
            for (Function<String, Integer> hashFunc : hashFunctions) {
                int position = hashFunc.apply(element);
                if (countArray[position] == 0) {
                    return false;
                }
            }
            return true;
        }

        // 支持删除操作（需确保元素确实存在，否则会影响其他元素）
        public void remove(String element) {
            for (Function<String, Integer> hashFunc : hashFunctions) {
                int position = hashFunc.apply(element);
                if (countArray[position] > 0) {
                    countArray[position]--;
                }
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        // 测试基础版
        BasicBloomFilter basicFilter = new BasicBloomFilter(1000, 0.01);
        basicFilter.add("apple");
        basicFilter.add("banana");
        System.out.println("基础版 - 是否包含apple: " + basicFilter.mightContain("apple")); // true
        System.out.println("基础版 - 是否包含orange: " + basicFilter.mightContain("orange")); // false
        System.out.println("估计误判率: " + basicFilter.estimateFalsePositiveRate(2)); // ~0.01

        // 测试可扩容版
        ScalableBloomFilter scalableFilter = new ScalableBloomFilter(10, 0.01);
        for (int i = 0; i < 100; i++) {
            scalableFilter.add("item" + i);
        }
        System.out.println("可扩容版 - 过滤器数量: " + scalableFilter.filters.size()); // 4（10→20→40→80→160）

        // 测试计数版（支持删除）
        CountingBloomFilter countingFilter = new CountingBloomFilter(100, 0.01, 10);
        countingFilter.add("test");
        System.out.println("计数版 - 添加后是否包含: " + countingFilter.mightContain("test")); // true
        countingFilter.remove("test");
        System.out.println("计数版 - 删除后是否包含: " + countingFilter.mightContain("test")); // false
    }
}

各版本优化说明

基础布隆过滤器：实现了核心功能，通过数学公式计算最优的位数组大小和哈希函数数量，平衡空间占用和误判率。适合元素数量已知且固定的场景。
可扩容布隆过滤器：通过维护多个过滤器实现动态扩容，解决了基础版无法处理元素数量超过预期的问题。新过滤器的误判率更低，保证整体误判率可控。适合元素数量动态增长的场景。
计数布隆过滤器：用整数数组替代位数组，支持元素删除操作（通过减少计数实现）。需注意：删除前需确保元素确实存在，否则会增加误判率；计数有上限，防止溢出。适合需要动态维护集合的场景。

实践建议

参数选择：根据预期元素数n和可接受误判率p计算最优m（位数组大小）和k（哈希函数数量）
哈希函数：选择相互独立的哈希函数（如使用不同盐值的 MurmurHash），减少哈希碰撞
容量规划：避免元素数量超过预期值，否则误判率会急剧上升
组合使用：可与其他数据结构配合（如布隆过滤器 + 哈希表），用布隆过滤器快速过滤不存在的元素，哈希表存储实际存在的元素以消除误判

布隆过滤器是处理海量数据存在性判断的高效工具，在缓存优化、数据去重等场景中不可替代。正确理解其概率性本质和误判特性，是合理应用的关键。