Simple scala Bloom filter. Uses MurmurHash3 to compute hashes.

BloomFilter.scala

import scala.collection.mutable.BitSet
import scala.util.hashing.{MurmurHash3 => MH3}
import scala.math.{abs, log}

class BloomFilter(n: Int, p: Double) {
  val m = (-n * log(p) / 0.48).toInt + 1
  val k = (0.7 * m / n).toInt
  val buckets = new BitSet(m)

  def add(elem: String) = hash(elem).forall(buckets += _)

  def query(elem: String) = hash(elem).exists(index => buckets.contains(index))

  private def hash(elem: String) = {
    val h1 = MH3.stringHash(elem)
    val h2 = MH3.stringHash(elem, h1)
    for (i <- 0 until k) yield abs((h1 + i * h2) % m)
  }
}