BloomFilter.optimal constructor

BloomFilter.optimal({ required int expectedItems, double falsePositiveRate = 0.01, })

Creates an optimally-sized Bloom filter for expectedItems with the given falsePositiveRate.

Formulas (from Bloom filter theory):

• m = -n * ln(p) / (ln(2)^2) (optimal bit count)
• k = (m / n) * ln(2) (optimal hash count)

where n = expected items, p = false positive rate.

Implementation

factory BloomFilter.optimal({
  required int expectedItems,
  double falsePositiveRate = 0.01,
}) {
  // Ensure sane minimums
  final n = math.max(expectedItems, 1);
  final p = falsePositiveRate.clamp(0.0001, 0.5);

  // Optimal bit count
  final m = (-(n * math.log(p)) / (math.ln2 * math.ln2)).ceil();
  // Clamp to at least 8 bits (1 byte) and at most 1MB
  final bitCount = m.clamp(8, 8 * 1024 * 1024);

  // Optimal hash count
  final k = ((bitCount / n) * math.ln2).ceil();
  // Clamp to 1..16 (SHA-256 gives us up to 8 hashes per digest,
  // we can double-hash for up to 16)
  final hashCount = k.clamp(1, 16);

  final byteCount = (bitCount + 7) ~/ 8; // Round up to full bytes
  return BloomFilter._(
    bits: Uint8List(byteCount),
    bitCount: bitCount,
    hashCount: hashCount,
  );
}