4

HatTrie の一種で使用する HashSet[Array[Byte]] を作成しているときに、この問題に出くわしました。

どうやら、配列の標準的な equals() メソッドは同一性をチェックします。要素がセットに含まれているかどうかを確認するために .deepEquals() を使用する代替 Comparator を HashSet に提供するにはどうすればよいですか?

基本的に、このテストに合格したい：

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 になるまでプロセスを繰り返します。0 になった時点でデータをノードに格納します。

ここで、この構造体を HashSet のベースとして使用し、配列を格納します。配列のハッシュ コードは偶数であるため、ツリーの左側に配置されます。正確な位置は無視しましょう。

後で配列を変更し、セットで検索します。ハッシュ コードが奇妙になり、ツリーの右側を見てみると、ツリーの反対側に保存されているにもかかわらず、見つけることができません。

したがって、ハッシュベースのコレクションで配列を使用しないでください。もちろん、これはあなたの質問に答えません。

あなたの質問に関しては、HashSet をサブクラス化し、equals メソッドをオーバーライドする必要があります。HashSet が final なのか、sealed クラスの子孫なのかがわからないため、これが実行可能かどうかもわかりません。

もう 1 つのオプションは、equals または "==" という名前ではなく、特に deepEquals に基づいて、別の比較メソッドを作成し、Pimp My Class メソッドを使用してそれを HashSet に追加することです。

編集

私は HashSet をサブクラス化することを意味していましたが、質問に十分な注意を払っていませんでした。contains を使用するだけでなく、HashSet 全体を比較していると思いました。あなたはこれを行うことができます：

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 に答える