4

在创建用于一种 HatTrie 的 HashSet[Array[Byte]] 时,我偶然发现了这个问题。

显然,数组上的标准 equals() 方法检查身份。如何为 HashSet 提供使用 .deepEquals() 来检查集合中是否包含元素的替代比较器?

基本上,我希望这个测试通过:

describe ("A HashSet of Byte Array") {      

    it("must contain arrays that are equivalent to one that has been added") {
        val set = new HashSet[Array[Byte]]()
        set += "ab".getBytes("UTF-8")
        set must contain ("ab".getBytes("UTF-8"))           
    }
}

我无法将 Array[Byte] 包装到另一个对象中,因为它们有很多。没有为此目的编写新的 HashSet 实现,我能做些什么吗?

4

1 回答 1

1

可变数据结构,例如数组,在使用哈希码的地方是禁忌的。这是因为数据结构可以改变,从而改变数据的哈希码,从而使得对数据的访问不准确。

例如,假设我有一个二叉树来根据它们的哈希码存储元素。如果哈希是偶数,我将数据存储在左侧,如果奇数则存储在右侧。然后我将哈希除以 2,并重复该过程直到哈希为 0,此时我将数据存储在节点中。

现在,我使用这个结构作为 HashSet 的基础,然后在上面存储一个数组。该数组具有偶数哈希码,因此它位于树的左侧。让我们忽略它的确切位置。

后来,我换了数组,然后在片场上查了一下。现在哈希码是奇怪的,我去树的右边看,因此找不到它,即使它存储在树中——就在另一边。

因此,不要将数组与基于散列的集合一起使用。当然,这不能回答你的问题。

至于你的问题,你必须继承 HashSet,然后重写 equals 方法。我不知道 HashSet 是最终的还是密封类的后代,所以我不知道这是否可行。

另一种选择是创建一个替代的比较方法——不命名为 equals 或“==”,专门基于 deepEquals,然后使用 Pimp My Class 方法将其添加到 HashSet。

编辑

我的意思是子类 HashSet,但我没有对这个问题给予足够的重视。我以为你是在比较整个 HashSet,而不是仅仅使用 contains。你可以这样做:

class MyHashSet[A] extends scala.collection.mutable.HashSet[A] {
  override def contains(elem: A): Boolean = elem match {
    case arr : Array[_] => this.elements exists (arr deepEquals _)
    case _ => super.contains(elem)
  }
}

这实际上在这里不起作用,因为没有遵循第一种情况。我真的迷路了,因为对 REPL 的简单测试似乎表明它应该可以工作。我认为这可能与拳击有关,但我不清楚是什么——否则我会让它起作用。:-)

于 2009-07-27T20:07:56.510 回答