HashSetでの代替比較の使用

Question

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"))   
    } 
} 

それらの多くがありますので、私は実行可能に別のオブジェクトへの配列[バイト]をラップすることはできません。この目的のために新しいHashSet実装を書くのに手間がかかりません。

Answer 1

配列などの変更可能なデータ構造は、ハッシュコードが使用されている場所での使用については反対です。これは、データ構造が変更される可能性があるため、データのハッシュコードが変更されるため、データへのアクセスが不正確になるためです。

たとえば、ハッシュコードに基づいて要素を格納するバイナリツリーがあるとします。ハッシュが偶数の場合は、右側に奇数の場合はデータを左側に格納します。次に、ハッシュを2で除算し、ハッシュが0になるまでプロセスを繰り返します。この時点で、ノードにデータが格納されます。

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

その後、私は配列を変更して、それをセットで調べます。今度はハッシュコードが奇妙なので、ツリーの右側を見て、ツリーの内側に格納されていても、それを見つけることはできません。

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

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

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

編集

私は、サブクラスのHashSetを意味したが、私は疑問に十分な注意を払っていません。私はあなたが含まれているだけでなく、全体の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の簡単なテストは、それが働くべきであることを示すようだ。私はそれがボクシングとは何かを持っているかもしれないと思っていますが、私は何が本当に明確ではない - または私はそれを働かせるだろう。 :-)