过滤器之布隆过滤器（Bloom Filter）

关于布隆过滤器的学习与思考

什么是布隆过滤器（Bloom Filter）？

布隆过滤器是一种概率型数据结构，用于判断一个元素是否在集合中。它实际上是一个长二进制向量和一系列随机映射函数。当一个元素被加入集合时，通过N个散列函数将这个元素映射成一个位数组中的 N个点（0->）。查数据时，经过散列函数计算出这些点，如果这些点中存在0，则被检元素一定不在；如果都是1，则被检元素可能在（有可能大集合中元素已被删除）。

关于布隆过滤器的优缺点如下：

• 优点：
  • 查询效率高，快速判断元素是否存在
  • 空间效率高，存储空间、插入、查询效率都很高
• 缺点：
  • 存在误判
  • 误判率由位数组长度和哈希函数数量决定，增加位数组长度和哈希函数数量相当于增加存储空间和查询时间
  • 删除元素困难

实际应用场景

布隆过滤器常用来解决如下问题：

• 解决Redis缓存穿透问题
• 黑名单过滤，可以用来做邮件黑名单过滤
• 解决推荐问题，推荐过的内容不再推荐（抖音、B站）
• 数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库的IO请求
• 网络爬虫对 URL 去重

---

常见的开源框架中的布隆过滤器（Bloom Filter）

• Google Guava：Guava 是 Google 的一个开源 Java 工具库，其中包含了布隆过滤器的实现。
• Apache HBase：HBase 是一个开源的、非关系型、分布式数据库，它是 Apache Software Foundation 的项目。HBase 使用布隆过滤器来减少磁盘查找。
• Redis：Redis 是一个开源的、内存中的数据结构存储系统，它可以用作数据库、缓存和消息代理。Redis 4.0 版本开始支持布隆过滤器插件。（Redission Bloom）

代码实现

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

public class BloomFilter {
    
    private BitSet bitSet;
    private int bitSetSize;
    private int numberOfHashFunctions;

    public BloomFilter(int bitSetSize, int numberOfHashFunctions) {
        this.bitSetSize = bitSetSize;
        this.numberOfHashFunctions = numberOfHashFunctions;
        this.bitSet = new BitSet(bitSetSize);
    }

    public void add(String s) {
        for (int i = 0; i < numberOfHashFunctions; i++) {
            int hashCode = getHash(s, i);
            // 根据哈希码 和 位集合 大小判断 目标位 的位置
            bitSet.set(Math.abs(hashCode % bitSetSize), true);
        }
    }

    public boolean contains(String s) {
        for (int i = 0; i < numberOfHashFunctions; i++) {
            int hashCode = getHash(s, i);
            // 如果有一个位置不符合，即 该元素不存在
            if (!bitSet.get(Math.abs(hashCode % bitSetSize))) {
                return false;
            }
        }
        return true;
    }

    private int getHash(String s, int i) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            // 使用 字符串 连接不同 数字 来表示多个哈希算法
            byte[] bytes = md.digest((s + Integer.toString(i)).getBytes());
            int hashCode = 0;
            for (int j = 0; j < bytes.length; j++) {
                hashCode += ((int) bytes[j] & 0xFF) << (8 * j);
            }
            return hashCode;
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("No such hashing algorithm", e);
        }
    }
}

测试代码如下：

public static void main(String[] args) {
    // 创建一个具有 1000 位的“数组”和 5 个哈希函数的布隆过滤器
    BloomFilter bloomFilter = new BloomFilter(1000, 5);
    // 添加字符串“test”
    bloomFilter.add("test");
    // 验证是否存在
    System.out.println(bloomFilter.contains("test")); // prints true
    System.out.println(bloomFilter.contains("anotherTest")); // prints false
}

参考

布隆过滤器 - 维基百科，自由的百科全书

布隆(Bloom Filter)过滤器——全面讲解，建议收藏

Redis布隆过滤器（原理+图解）

布隆过滤器 (Bloom Filter) 详解