Блог

Я пытаюсь смоделировать фильтр блума в Scala. Сама логика на самом деле довольно проста, но я изо всех сил пытаюсь понять, как адекватно использовать структуры данных Scala, чтобы сделать их красивыми, идиоматичными и функциональными.

Моя проблема заключается в следующем: если я использую класс case, мне нужен конструктор для генерации хэш-функций и массива bits, в котором будут храниться фактические данные фильтра Блума. Но затем, в таком методе, как «add», который изменит содержимое массива bits, мне нужно вернуть новый фильтр блума вместо изменения содержимого существующего, чтобы мой метод был ссылочно прозрачным.

К сожалению, я не могу создать новый фильтр Блума, потому что я не хочу, чтобы новый заново создавал новый массив bits и новые хэш-функции, и я также не могу передать ему существующие, потому что ни массив bits, ни хэш-функции не являются частью класса case фильтра Блума.

Итак, как я должен смоделировать это в Scala?

[ Изменено для использования 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 обращаетесь к фильтру.

Очевидно, что это можно сделать значительно более эффективным как с точки зрения скорости, так и с точки зрения использования памяти.