Trivial bloom filter implementation in Scala.

Bloom.scala

class BloomSet[A] private (val size: Int, val k: Int,private val contents: Vector[Boolean]){
  
  val width = contents.length
 
  def this(width: Int, k: Int) = this(0, k, BloomSet.alloc(width))

  def contains(e:Any) = {
    (0 to k).foldLeft(true) { (acc,i) =>
      acc && contents(hash(e,i,width))
    }
  }

  def hash(e:Any, iters:Int, bounds:Int): Int = {
    Math.abs(
      if (iters == 0) e.hashCode
      else iters ^ hash(e,iters-1,bounds)) % bounds
  }

  protected def add(contents: Vector[Boolean])(e:Any) = {
    var back = contents

    for(i <- 0 to k) {
      val hashed = hash(e,i,width)
      back = back.updated(hashed,true)
    }
    back
  }

  def +(e:Any) = new BloomSet[A](size + 1, k, add(contents)(e))

}
 
object BloomSet {
  def alloc(size: Int) = {
    (0 until size).foldLeft(Vector[Boolean]()) { (c:Vector[Boolean],i:Int) => false+:c } 
  }

  def main(args:Array[String]){
    var bf = new BloomSet(40,4);

    bf = List("hi","hello","today").foldLeft(bf)((fil,st)=> fil+st)
    
    println(bf.contains("hi"))
    println(bf.contains("hello"))
    println(bf.contains("never"))
  }
}