🥮 mooncakes.io
    Sign in

    BloomierFilter

    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Last updated
    last year
    Downloads
    26

    #Bloomier Filter

    English | 简体中文

    A Bloomier Filter implementation in MoonBit that extends the traditional Bloom Filter to support key-value storage. This probabilistic data structure allows you to store and retrieve values associated with keys while maintaining space efficiency and fast operations.

    #🚀 Key Features

    • 🗃️ Key-Value Storage – Store and retrieve values associated with keys • ⚡ Fast Operations – O(1) average time for insert and query operations • 🎯 Probabilistic Queries – Handles uncertain results gracefully • 📊 Space Efficient – Compact storage with configurable false positive rates • 🔧 Flexible Configuration – Customizable parameters for different use cases • 🔄 Batch Operations – Support for bulk insert and query operations • 💾 Serialization – Save and load filter state to/from storage • 🔍 Type Safety – Generic implementation with Hash and Eq trait support

    #📥 Installation

    moon add SupremeHuaji/BloomierFilter

    #🚀 Usage Guide

    #🔨 Create

    You can create a BloomierFilter using configuration parameters.

      let config = BloomierConfig::{
        expected_elements: 1000,
        false_positive_rate: 0.01,
        hash_functions: None,  // Auto-calculate optimal count
      }
      let filter = @BloomierFilter.new(config)

      // Or create from existing data
      let items = [("apple", "red"), ("banana", "yellow"), ("grape", "purple")]
      let filter2 = @BloomierFilter.from_array(items, config)

    #➕ Insert Key-Value Pairs

    Use the insert() method to add key-value pairs to the filter.

      let config = BloomierConfig::{
        expected_elements: 100,
        false_positive_rate: 0.01,
        hash_functions: Some(3),
      }
      let filter = @BloomierFilter.new(config)

      match filter.insert("fruit", "apple") {
        InsertResult::Success => println("插入成功")
        InsertResult::NeedRehash => println("需要重新哈希")
        InsertResult::Failure => println("插入失败")
      }

    #👀 Query Operations

    Retrieve values associated with keys, handling probabilistic results.

      let config = BloomierConfig::{
        expected_elements: 100,
        false_positive_rate: 0.01,
        hash_functions: Some(3),
      }
      let filter = @BloomierFilter.from_array([
        ("name", "Alice"), ("age", "25"), ("city", "Beijing")
      ], config)

      match filter.get("name") {
        QueryResult::Found(value) => println("找到值: \{value}")
        QueryResult::Uncertain => println("结果不确定，可能存在冲突")
        QueryResult::NotFound => println("键不存在")
      }

      // Simple existence check
      if filter.contains("age") {
        println("年龄信息存在")
      }

    #🔍 Advanced Queries

    Get all possible values for a key in case of hash collisions.

      let config = BloomierConfig::{
        expected_elements: 10,
        false_positive_rate: 0.01,
        hash_functions: Some(2),
      }
      let filter = @BloomierFilter.from_array([
        ("a", "1"), ("b", "2"), ("c", "3")
      ], config)

      println("过滤器大小: \{filter.size()}")
      println("负载因子: \{filter.load_factor()}")

      if filter.needs_resize(0.8) {
        println("建议扩容")
      }

      let stats = filter.stats()
      println("统计信息: \{stats}")

    #📏 Size & Status

    Check the current size and status of the filter.

      let config = BloomierConfig::{
        expected_elements: 10,
        false_positive_rate: 0.01,
        hash_functions: Some(2),
      }
      let filter = @BloomierFilter.from_array([
        ("a", "1"), ("b", "2"), ("c", "3")
      ], config)

      println("过滤器大小: \{filter.size()}")
      println("负载因子: \{filter.load_factor()}")

      if filter.needs_resize(0.8) {
        println("建议扩容")
      }

      let stats = filter.stats()
      println("统计信息: \{stats}")

    #🧹 Clear

    Remove all elements from the filter.

      let config = BloomierConfig::{
        expected_elements: 10,
        false_positive_rate: 0.01,
        hash_functions: Some(2),
      }
      let filter = @BloomierFilter.from_array([("x", "10"), ("y", "20")], config)
      println("清空前大小: \{filter.size()}")

      filter.clear()
      println("清空后大小: \{filter.size()}")
      assert_true!(filter.is_empty())

    #🔄 Batch Operations

    Perform bulk insert and query operations for better efficiency.

      let config = BloomierConfig::{
        expected_elements: 20,
        false_positive_rate: 0.01,
        hash_functions: Some(3),
      }
      let filter = @BloomierFilter.new(config)

      // Batch insert
      let items = [("user1", "admin"), ("user2", "guest"), ("user3", "user")]
      let results = filter.insert_all(items)

      for i = 0; i < results.length(); i = i + 1 {
        let (key, _) = items[i]
        match results[i] {
          InsertResult::Success => println("\{key} 插入成功")
          _ => println("\{key} 插入遇到问题")
        }
      }

      // Batch query
      let keys = ["user1", "user2", "user3", "user4"]
      let query_results = filter.get_all(keys)
      for i = 0; i < query_results.length(); i = i + 1 {
        match query_results[i] {
          QueryResult::Found(value) => println("\{keys[i]} -> \{value}")
          _ => println("\{keys[i]} 未找到或不确定")
        }
      }

    #🔄 Value Iteration

    Iterate over all stored values.

      let config = BloomierConfig::{
        expected_elements: 10,
        false_positive_rate: 0.01,
        hash_functions: Some(2),
      }
      let filter = @BloomierFilter.from_array([
        ("language", "MoonBit"), ("paradigm", "functional"), ("type", "static")
      ], config)

      // Iterate through all values
      filter.iter_values(fn(value) {
        println("存储的值: \{value}")
      })

      // Collect all values to array
      let all_values = filter.values()
      println("所有值: \{all_values}")

    #💾 Serialization

    Save and restore filter state for persistence.

      let config = BloomierConfig::{
        expected_elements: 10,
        false_positive_rate: 0.01,
        hash_functions: Some(2),
      }
      let filter = @BloomierFilter.from_array([
        ("session1", "active"), ("session2", "expired")
      ], config)

      // Serialize
      let serialized = filter.serialize()
      println("序列化版本: \{serialized.version}")

      // Deserialize
      let restored_filter : @BloomierFilter.BloomierFilter[String, String] =
        @BloomierFilter.deserialize(serialized)

      println("恢复后大小: \{restored_filter.size()}")
      assert_eq!(restored_filter.size(), filter.size())

    #🔧 Rehashing and Resizing

    Handle capacity issues and optimization.

      let config = BloomierConfig::{
        expected_elements: 10,
        false_positive_rate: 0.05,
        hash_functions: Some(2),
      }
      let filter = @BloomierFilter.new(config)
      let items = [("key1", "val1"), ("key2", "val2"), ("key3", "val3")]

      // Insert initial data
      for item in items {
        let (key, value) = item
      ignore(filter.insert(key, value))
      }

      // Rehash with same data if needed
      filter.rehash_with_items(items)

      // Resize to larger capacity
      let original_size = filter.stats().table_size
      filter.resize(original_size * 2, items)
      println("新表大小: \{filter.stats().table_size}")

    #🎯 Handling Uncertainty

    Deal with probabilistic nature of Bloomier Filters.

      let config = BloomierConfig::{
        expected_elements: 20,
        false_positive_rate: 0.1,
        hash_functions: Some(2),
      }
      let filter = @BloomierFilter.new(config)
      ignore(filter.insert("ambiguous", "value1"))
      // Due to hash collisions, queries might be uncertain

      match filter.get("ambiguous") {
        QueryResult::Found(value) => {
          println("确定找到: \{value}")
        }
        QueryResult::Uncertain => {
          println("结果不确定，可能的值:")
          let possible_values = filter.get_all_values("ambiguous")
          for value in possible_values {
            println("  - \{value}")
          }
        }
        QueryResult::NotFound => {
          println("确定不存在")
        }
      }

    #📊 Performance Characteristics

    OperationTime ComplexitySpace Complexity
    @BloomierFilter.new()O(m)O(m)
    insert()O(k)O(1)
    get() / contains()O(k)O(1)
    get_all_values()O(k)O(k)
    clear()O(m)O(1)
    insert_all()O(n×k)O(1)
    serialize()O(m)O(m)

    Where:
    • n = number of elements
    • m = table size
    • k = number of hash functions

    #🏗️ Implementation Details

    This Bloomier Filter is implemented using:
    • Hash Table Array: Stores actual values in Option[V] slots
    • Multiple Hash Functions: Uses configurable number of hash functions with different seeds
    • Conflict Resolution: Attempts multiple hash locations and supports rehashing
    • Probabilistic Guarantees: May return uncertain results due to hash collisions

    The implementation uses MoonBit's built-in hashing with custom seeds to generate multiple hash functions for each key.

    #🎛️ Configuration Options

    #BloomierConfig Parameters

    BloomierConfig::{
      expected_elements: Int,        // Expected number of key-value pairs
      false_positive_rate: Double,   // Desired false positive rate (0.0 to 1.0)
      hash_functions: Option[Int],   // Number of hash functions (None for auto)
    }

    #Recommended Settings

    • Small datasets (< 1000): false_positive_rate: 0.01, hash_functions: Some(3)
    • Medium datasets (1000-10000): false_positive_rate: 0.001, hash_functions: None
    • Large datasets (> 10000): false_positive_rate: 0.0001, hash_functions: None

    #🆚 Bloom Filter vs Bloomier Filter

    FeatureBloom FilterBloomier Filter
    StorageBits onlyKey-value pairs
    Query ResultBoolQueryResult[V]
    False Positives"Maybe exists""Maybe wrong value"
    Space UsageVery lowModerate
    Use CasesSet membershipAssociative cache

    #📜 License

    This project is licensed under the Apache-2.0 License. See LICENSE for details.

    BloomierConfig

    source
    pub(all) struct BloomierConfig {
      expected_elements : Int
      false_positive_rate : Double
      hash_functions : Int?
    }

    Bloomier Filter 的配置参数

    BloomierError

    source
    pub(all) enum BloomierError {
      InsufficientCapacity
      UnresolvableConflict
      InvalidParameters(String)
      BuildFailure(String)
    }

    错误类型
    impl Eq for BloomierError

    BloomierFilter

    source
    pub struct BloomierFilter[K, V] {
      table : Array[V?]
      table_size : Int
      hash_count : Int
      seeds : Array[Int]
      size : Int
    }

    Bloomier Filter 数据结构 支持存储键值对并进行快速查询
    impl Eq for BloomierFilter[K, V]
    impl Show for BloomierFilter[K, V]

    BloomierFilter::clear

    source
    fn[K, V] BloomierFilter::clear(self : BloomierFilter[K, V]) -> Unit

    清空过滤器

    Example

    filter.clear()
assert_eq!(filter.size(), 0)

    BloomierFilter::contains

    source
    fn[K : Hash + Eq, V] BloomierFilter::contains(self : BloomierFilter[K, V], key : K) -> Bool

    检查键是否可能存在

    Example

    if filter.contains("key") {
  println("键可能存在")
} else {
  println("键一定不存在")
}

    BloomierFilter::get

    source
    fn[K : Hash + Eq, V] BloomierFilter::get(self : BloomierFilter[K, V], key : K) -> QueryResult[V]

    查询键对应的值

    Example

    match filter.get("key") {
  Found(value) => println("找到值: \{value}")
  NotFound => println("未找到")
  Uncertain => println("可能存在")
}

    BloomierFilter::get_all

    source
    fn[K : Hash + Eq, V] BloomierFilter::get_all(self : BloomierFilter[K, V], keys : Array[K]) -> Array[QueryResult[V]]

    批量查询

    BloomierFilter::get_all_values

    source
    fn[K : Hash + Eq, V] BloomierFilter::get_all_values(self : BloomierFilter[K, V], key : K) -> Array[V]

    获取所有可能的值

    BloomierFilter::insert

    source
    fn[K : Hash + Eq, V] BloomierFilter::insert(self : BloomierFilter[K, V], key : K, value : V) -> InsertResult

    插入键值对

    Example

    match filter.insert("key", "value") {
  Success => println("插入成功")
  Failure => println("插入失败")
  NeedRehash => println("需要重新哈希")
}

    BloomierFilter::insert_all

    source
    fn[K : Hash + Eq, V] BloomierFilter::insert_all(self : BloomierFilter[K, V], items : Array[(K, V)]) -> Array[InsertResult]

    批量插入

    BloomierFilter::is_empty

    source
    fn[K, V] BloomierFilter::is_empty(self : BloomierFilter[K, V]) -> Bool

    检查过滤器是否为空

    Example

    if filter.is_empty() {
  println("过滤器为空")
}

    BloomierFilter::iter_values

    source
    fn[K, V] BloomierFilter::iter_values(self : BloomierFilter[K, V], f : (V) -> Unit) -> Unit

    迭代所有非空值

    BloomierFilter::load_factor

    source
    fn[K, V] BloomierFilter::load_factor(self : BloomierFilter[K, V]) -> Double

    获取负载因子

    BloomierFilter::needs_resize

    source
    fn[K, V] BloomierFilter::needs_resize(self : BloomierFilter[K, V], threshold : Double) -> Bool

    检查是否需要扩容

    BloomierFilter::rehash_with_items

    source
    fn[K : Hash + Eq, V] BloomierFilter::rehash_with_items(self : BloomierFilter[K, V], items : Array[(K, V)]) -> Unit

    带外部数据的重哈希

    BloomierFilter::resize

    source
    fn[K : Hash + Eq, V] BloomierFilter::resize(self : BloomierFilter[K, V], new_size : Int, items : Array[(K, V)]) -> Unit

    动态调整表大小

    BloomierFilter::serialize

    source
    fn[K, V : Eq] BloomierFilter::serialize(self : BloomierFilter[K, V]) -> SerializedBloomier[V]

    序列化过滤器

    Example

    let serialized = filter.serialize()

    BloomierFilter::size

    source
    fn[K, V] BloomierFilter::size(self : BloomierFilter[K, V]) -> Int

    获取过滤器大小

    Example

    println("当前存储了 \{filter.size()} 个元素")

    BloomierFilter::stats

    source
    fn[K, V] BloomierFilter::stats(self : BloomierFilter[K, V]) -> BloomierStats

    获取统计信息

    Example

    let stats = filter.stats()
println("负载因子: \{stats.load_factor}")

    BloomierFilter::values

    source
    fn[K, V] BloomierFilter::values(self : BloomierFilter[K, V]) -> Array[V]

    收集所有值到数组

    BloomierStats

    source
    pub struct BloomierStats {
      table_size : Int
      stored_elements : Int
      load_factor : Double
      hash_functions : Int
      free_slots : Int
    }

    统计信息
    impl Eq for BloomierStats

    HashResult

    source
    pub struct HashResult {
      hashes : Array[Int]
    }

    哈希函数的结果

    InsertResult

    source
    pub(all) enum InsertResult {
      Success
      Failure
      NeedRehash
    }

    插入操作的结果
    impl Eq for InsertResult

    QueryResult

    source
    pub(all) enum QueryResult[V] {
      Found(V)
      NotFound
      Uncertain
    }

    查询操作的结果
    impl Eq for QueryResult[V]
    impl Show for QueryResult[V]

    SerializedBloomier

    source
    pub struct SerializedBloomier[V] {
      table_data : Array[V?]
      table_size : Int
      hash_count : Int
      seeds : Array[Int]
      version : Int
    }

    序列化格式

    deserialize

    source
    fn[K, V] deserialize(data : SerializedBloomier[V]) -> BloomierFilter[K, V]

    从序列化数据反序列化

    Example

    let filter = @BloomierFilter.deserialize(serialized_data)!

    from_array

    source
    fn[K : Hash + Eq, V] from_array(items : Array[(K, V)], config : BloomierConfig) -> BloomierFilter[K, V]

    从键值对数组创建 Bloomier Filter

    Example

    let items = [("key1", "value1"), ("key2", "value2")]
let filter = @BloomierFilter.from_array(items, config)

    new

    source
    fn[K : Hash + Eq, V] new(config : BloomierConfig) -> BloomierFilter[K, V]

    创建新的 Bloomier Filter

    Example

    let config = { expected_elements: 1000, false_positive_rate: 0.01, hash_functions: None }
let filter = @BloomierFilter.new(config)

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io