2012-08-07 27 views
5

アロハ、HashSetの<T> .RemoveWhere()とGetHashCodeメソッド()

はここGetHashCodeメソッドをオーバーライドする単純なクラスです:私は、そのクラスのインスタンスを作成する場合は、HashSetのに追加

class OverridesGetHashCode 
{ 
    public string Text { get; set; } 

    public override int GetHashCode() 
    { 
     return (Text != null ? Text.GetHashCode() : 0); 
    } 
    // overriding Equals() doesn't change anything, so I'll leave it out for brevity 
} 

、その後、このように、Textプロパティを変更します。

var hashset = new HashSet<OverridesGetHashCode>(); 
var oghc = new OverridesGetHashCode { Text = "1" }; 
hashset.Add(oghc); 
oghc.Text = "2"; 

を、これは動作しません:

var removedCount = hashset.RemoveWhere(c => ReferenceEquals(c, oghc)); 
// fails, nothing is removed 
Assert.IsTrue(removedCount == 1); 

とどちらが行い、この:

// this line works, i.e. it does find a single item matching the predicate 
var existing = hashset.Single(c => ReferenceEquals(c, oghc)); 
// but this fails; nothing is removed again 
var removed = hashset.Remove(existing); 
Assert.IsTrue(removed); 

私はそれが内部的に項目が挿入され、それが本当ならば、それはhashset.Contains(oghc)が動作しないことは理解 だ時に生成された使用ハッシュを推測します。 また、ハッシュコードで項目を検索し、一致するものが見つかった場合にのみ、述語をチェックして、最初のテストが失敗する理由が考えられます(ここでもまた推測しています)。 しかし、なぜ最後のテストが失敗するのですか、私はちょうどハッシュセットからそのオブジェクトを持っていますか?私は何かを見逃していますか、これはHashSetから何かを削除するための間違った方法ですか?

この度は読んでいただきありがとうございます。

UPDATE:そのオブジェクトはHashSetの契約に違反しているHashSetに使用されている間、あなたのオブジェクトのハッシュコードを変更することにより

protected bool Equals(OverridesGetHashCode other) 
    { 
     return string.Equals(Text, other.Text); 
    } 

public override bool Equals(object obj) 
    { 
     if (ReferenceEquals(null, obj)) return false; 
     if (ReferenceEquals(this, obj)) return true; 
     if (obj.GetType() != this.GetType()) return false; 
     return Equals((OverridesGetHashCode) obj); 
    } 
+0

Eric Lippertの[GetHashCodeのガイドラインとルール](http://blogs.msdn.com/b/ericlippert/archive/2011/02/28/guidelines-and-rules-for- gethashcode.aspx)特に* GetHashCodeによって返されたルールは、安定したままのハッシュコードに依存するデータ構造体にオブジェクトが含まれている間は変更してはいけません。 –

+0

私は最初これが良い質問だったと思ったので、私は何か本当にばかげて尋ねたような気分になりました:)しばらくしてから意味があります。 「私はHashSetを使用したことがありません」と私が思いつくべき最善の言い訳です:Dありがとうございます。 –

答えて

2

良い回答があり、これを追加したいだけです。

  1. 値のハッシュコードを取得するにはIEqualityComparer<T>.GetHashCode()を呼び出し:あなたが逆コンパイルHashSet<T>コードを見れば、あなたはAdd(value)には、次のないことがわかります。デフォルトの比較者の場合、これはGetHashCode()になります。
  2. (参照先)値を格納する "バケット"と "スロット"を計算するためにハッシュコードを使用します。
  3. 参照を格納します。

Remove(value)に電話すると、手順1.と2.を再度実行して、参照先の場所を確認します。次に、IEqualityComparer<T>.Equals()を呼び出して、実際に正しい値が見つかったことを確認します。ただし、GetHashCode()が返す値を変更したため、無効なバケット/スロット位置が計算されます。したがって、オブジェクトを見つけることができません。

したがって、Equals()は、ハッシュコードが変更された場合でも右のバケット/スロット位置に到達することは決してないため、実際にはここには入っていません。

4

:混乱を避けるために、ここで等号を()です。

オブジェクトを削除できないことはここで問題になりません。 最初にハッシュコードを変更することはできません。

私はMSDNから引用してみましょう:

が一貫していれば、オブジェクトの状態への変更はありませんよう は、戻り値を決定するのと同じ ハッシュコードを返ししなければならないオブジェクトのGetHashCodeメソッドオブジェクトのEqualsメソッドの これは、アプリケーションの現在の実行に対してのみtrueであり、 は、アプリケーションが で再度実行された場合に異なるハッシュコードが返されることに注意してください。

彼らは物語を少しずつ伝えますが、本質は同じです。彼らは言う、ハッシュコード決して変更することができます。実際には、もう誰も古いハッシュコードを使用しないようにしておけば、それを変更することができます。これは良い習慣ではないが、うまくいく。

+1

オブジェクトのEqualsメソッドの戻り値を決定するオブジェクト状態への変更があったと主張することができます* –

+0

編集した見積もりはここではまったく異なる問題です。同じデータを持つオブジェクトは同じハッシュコードを返さなければなりませんが、オブジェクトが異なるデータを持っているので、異なるハッシュコードを返す権利があります。 – Servy

+0

@Usr "オブジェクトのEquals 'の戻り値を決定するオブジェクト状態の変更がない限り、おそらく、オブジェクトがTextの値に基づいて等しいかどうか比較されている場合、GetHashCode() – drch

4

ハッシュベースのテーブル(HashSetDictionaryなど)に追加されたアイテムは、一度構造に挿入すると変更されません(少なくとも削除されない限り)。

データ構造内のオブジェクトを見つけるために、オブジェクトはハッシュコードを計算し、そのハッシュコードに基づいて場所を見つけます。そのオブジェクトを変更すると、それが返すハッシュコードは、そのデータ構造内の現在の位置を反映しなくなります(あなたが非常に、非常に運が良ければ、ちょうどハッシュ衝突である場合を除き)。 MSDN page for Dictionary

さは言う:

限り、オブジェクトがDictionary<TKey, TValue>でキーとして使用されているとして、それは、そのハッシュ値に影響を与える任意の方法で変更してはなりません。

この同じアサーションは、両方ともハッシュテーブルを使用して実装されているため、HashSetにも適用されます。

+0

上記の例では、hashset.RemoveWhere(x => true)を実行すると、述語は真ですが、ハッシュセットはオブジェクトを見つけることができません。 – drch

関連する問題