如何在Scala中对bloom filter建模

Question

我正在尝试在Scala中为bloom filter建模。逻辑本身实际上非常简单，但我正在努力弄清楚如何充分利用Scala的数据结构，使其更好、更实用、更实用。

我的问题是:如果我使用一个case类，我需要构造函数来生成哈希函数和存储实际布隆过滤器数据的位数组。但是，在像"add“这样会更改位数组内容的方法中，我需要返回一个新的布隆过滤器，而不是改变现有布隆过滤器的内容，以便我的方法在引用上是透明的。

不幸的是，我不能构造新的布隆过滤器，因为我不希望新的布隆过滤器重新创建新的位数组和新的散列函数，我也不能传递现有的，因为位数组和散列函数都不是布隆过滤器案例类的一部分。

那么，我应该如何在Scala中对此进行建模呢？

Answer 1

修改为使用BitSet，以下注释

这是它可能的工作原理的概述。

trait HashFunctions[T] {
  def apply(value: T): BitSet
}

object Bloom {
  class BloomFactory[T](hash: HashFunctions[T]) {
    case class Bloom(flags: BitSet) {
      def add(value: T): Bloom =
        Bloom(flags union hash(value))
      def test(value: T): Boolean =
        hash(value).subsetOf(flags)
    }
  }

  def apply[T](): BloomFactory[T]#Bloom = new BloomFactory(DefaultHashFunctions[T]).Bloom(BitSet.empty)
}

请注意，这样做确实会在每次添加一个值时创建一个新的Bloom，但这会使类变得不可变，这是一个好主意。散列函数是在伴生对象中创建的，这样就不会在每次add到过滤器时发生这种情况。

显然，这在速度和内存使用方面都可以显著提高效率。