Class BloomFilter<T>

java.lang.Object
cloud.opencode.base.cache.protection.BloomFilter<T>
Type Parameters:
T - the type of elements | 元素类型
public class BloomFilter<T> extends Object
Bloom Filter - Probabilistic data structure for cache penetration prevention 布隆过滤器 - 用于防止缓存穿透的概率数据结构

Space-efficient probabilistic data structure to test set membership.

空间高效的概率数据结构，用于测试集合成员关系。

Features | 主要功能:

  • False positive possible, false negative impossible - 可能误判存在，不会误判不存在
  • O(k) add and query - O(k) 添加和查询
  • Space efficient - 空间高效
  • Configurable false positive rate - 可配置误判率

Usage Examples | 使用示例:

BloomFilter<String> filter = new BloomFilter<>(100000, 0.01);
filter.add("existing-key");

// Before cache lookup - 缓存查询前
if (!filter.mightContain(key)) {
    return null; // Definitely not exists - 一定不存在
}
return cache.get(key); // Might exist - 可能存在

Performance | 性能特性:

  • Time complexity: O(k) where k is hash count - 时间复杂度: O(k) k 为哈希次数
  • Space complexity: O(m) bits - 空间复杂度: O(m) 位

Security | 安全性:

  • Thread-safe: Yes (uses AtomicLongArray with CAS) - 线程安全: 是（使用AtomicLongArray和CAS）
  • Null-safe: No (throws on null) - 空值安全: 否（null 时抛异常）
Since:
JDK 25, opencode-base-cache V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    BloomFilter(int bitSize, int hashCount)
    Create bloom filter with specific bit size and hash count 使用特定位大小和哈希次数创建布隆过滤器
    BloomFilter(long expectedInsertions, double fpp)
    Create bloom filter with expected insertions and false positive probability 使用预期插入数和误判率创建布隆过滤器

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(T element)
    Add element to filter 添加元素到过滤器
    void
    addAll(Collection<? extends T> elements)
    Add all elements 批量添加元素
    long
    approximateElementCount()
    Get approximate element count 获取近似元素数
    int
    bitSize()
    Get bit size 获取位大小
    void
    clear()
    Clear the filter 清空过滤器
    static <T> BloomFilter<T>
    create(long expectedInsertions)
    Create bloom filter for expected insertions with 1% FPP 创建预期插入数的布隆过滤器（1% 误判率）
    static <T> BloomFilter<T>
    create(long expectedInsertions, double fpp)
    Create bloom filter with custom FPP 创建自定义误判率的布隆过滤器
    double
    expectedFpp()
    Get expected false positive probability based on current insertions 获取基于当前插入数的预期误判率
    int
    hashCount()
    Get hash count 获取哈希次数
    void
    merge(BloomFilter<T> other)
    Merge another bloom filter into this one 合并另一个布隆过滤器
    boolean
    mightContain(T element)
    Check if element might be in the filter 检查元素可能存在于过滤器中

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • BloomFilter

      public BloomFilter(long expectedInsertions, double fpp)
      Create bloom filter with expected insertions and false positive probability 使用预期插入数和误判率创建布隆过滤器
      Parameters:
      expectedInsertions - expected number of insertions | 预期插入数
      fpp - false positive probability (0 < fpp < 1) | 误判率

    • BloomFilter

      public BloomFilter(int bitSize, int hashCount)
      Create bloom filter with specific bit size and hash count 使用特定位大小和哈希次数创建布隆过滤器
      Parameters:
      bitSize - number of bits | 位数
      hashCount - number of hash functions | 哈希函数数

  • Method Details

    • add

      public boolean add(T element)
      Add element to filter 添加元素到过滤器
      Parameters:
      element - the element | 元素
      Returns:
      true if bits changed (element was new) | 位改变返回 true（元素是新的）

    • mightContain

      public boolean mightContain(T element)
      Check if element might be in the filter 检查元素可能存在于过滤器中
      Parameters:
      element - the element | 元素
      Returns:
      true if element might exist, false if definitely not | 可能存在返回 true，一定不存在返回 false

    • addAll

      public void addAll(Collection<? extends T> elements)
      Add all elements 批量添加元素
      Parameters:
      elements - the elements | 元素集合

    • expectedFpp

      public double expectedFpp()
      Get expected false positive probability based on current insertions 获取基于当前插入数的预期误判率
      Returns:
      expected FPP | 预期误判率

    • approximateElementCount

      public long approximateElementCount()
      Get approximate element count 获取近似元素数
      Returns:
      approximate count | 近似数量

    • merge

      public void merge(BloomFilter<T> other)
      Merge another bloom filter into this one 合并另一个布隆过滤器
      Parameters:
      other - the other filter | 另一个过滤器
      Throws:
      IllegalArgumentException - if filters are incompatible | 过滤器不兼容时抛出异常

    • clear

      public void clear()
      Clear the filter 清空过滤器

    • bitSize

      public int bitSize()
      Get bit size 获取位大小
      Returns:
      bit size | 位大小

    • hashCount

      public int hashCount()
      Get hash count 获取哈希次数
      Returns:
      hash count | 哈希次数

    • create

      public static <T> BloomFilter<T> create(long expectedInsertions)
      Create bloom filter for expected insertions with 1% FPP 创建预期插入数的布隆过滤器（1% 误判率）
      Type Parameters:
      T - element type | 元素类型
      Parameters:
      expectedInsertions - expected insertions | 预期插入数
      Returns:
      bloom filter | 布隆过滤器

    • create

      public static <T> BloomFilter<T> create(long expectedInsertions, double fpp)
      Create bloom filter with custom FPP 创建自定义误判率的布隆过滤器
      Type Parameters:
      T - element type | 元素类型
      Parameters:
      expectedInsertions - expected insertions | 预期插入数
      fpp - false positive probability | 误判率
      Returns:
      bloom filter | 布隆过滤器