Set/bloom_filter library

🌸 Bloom Filter Implementation for High-Performance Data Filtering

A production-ready, enterprise-level implementation of Bloom filters that provides efficient probabilistic data structure for membership testing with configurable false positive rates. This implementation is optimized for high-throughput applications, distributed systems, and memory-constrained environments.

Features:

  • Generic type support for any hashable data type
  • Configurable false positive rate and optimal sizing
  • Multiple hash function strategies (MurmurHash, FNV, Jenkins)
  • Thread-safe operations for concurrent environments
  • Memory-efficient bit array representation
  • Automatic hash function optimization
  • Support for custom hash functions and salt values
  • Built-in performance monitoring and statistics
  • Serialization for persistence and network transmission
  • Union and intersection operations between filters

Time Complexity:

  • Insertion: O(k) where k is number of hash functions
  • Membership test: O(k) where k is number of hash functions
  • Union/Intersection: O(m) where m is bit array size

Space Complexity: O(m) where m is optimally sized bit array

Example:

final bloomFilter = BloomFilter<String>.optimal(
  expectedElements: 10000,
  falsePositiveRate: 0.01,
);
bloomFilter.add('user123');
final exists = bloomFilter.contains('user123'); // true
final notExists = bloomFilter.contains('user456'); // false (with 1% false positive rate)

Classes

BloomFilter<T>
Production-ready Bloom Filter implementation
BloomFilterConfig
Bloom Filter configuration for optimal performance

Typedefs

HashFunction<T> = int Function(T data, int seed)
Hash function type definition