scala - 在 HashSet 中使用替代比较

Question

我在创建 HashSet[Array[Byte]] 以在某种 HatTrie 中使用时偶然发现了这个问题。

显然，数组上的标准 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 实现，我能做些什么吗？

Answer 1

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

例如，假设我有一个二叉树来存储基于哈希码的元素。如果散列是偶数，我将数据存储在左侧，如果奇数存储在右侧。然后我将哈希除以二，重复这个过程直到哈希为 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 的简单测试似乎表明它应该可以工作。我想这可能与拳击有关，但我不太清楚是什么 - 否则我会让它起作用。 :-)