Self-optimizing Bloom filter

optimalBloomFilter

import { BloomFilter } from 'bloomfilter' // https://github.com/jasondavies/bloomfilter.js

/**
 * Returns an optimally configured Bloom filter for the given number of elements, using the
 * calculations from https://www.di-mgt.com.au/bloom-filter.html .
 * @param n The number of elements to be added to the Bloom filter
 * @param p The target false positive rate
 */
const optimalBloomFilter = (n: number, p: number = 0.01) => {
  const LOG2 = Math.log(2)
  const m = Math.ceil((n * Math.log(p)) / Math.log(1 / 2 ** LOG2))
  const m2 = nextPowerOf2(m)
  const k = Math.ceil((LOG2 * m) / n)
  console.log({ n, m, m_round: m2, k, p })
  return new BloomFilter(m2, k)
}

const nextPowerOf2 = (m: number) => 2 ** Math.ceil(Math.log2(m - 1))