6

2 つのインスタンスが与えられ、それぞれが同じ内容を持ち、任意の順序で挿入できるDictionary<long, string>コレクションを使用する必要があります。d1d2KeyValuePair<long, string>

  1. (d1 == d2)に評価されますtrue
  2. d1.GetHashCode()==d2.GetHashCode()

最初の要件はSortedDictionary、通常の の代わりに を使用することで最も簡単に達成できましたDictionary。

2 番目の要件が必要なのは、保存する必要がある 1 つのポイントがあるためですDictionary<Dictionary<long, string>, List<string>。メインのDictionary型は別のキーとして使用されDictionary、HashCodes が同一の内容に基づいて評価されない場合、使用は希望どおりに機能しませんContainsKey()。 (つまりd1、 をキーとして辞書に挿入されたアイテムが既に存在する場合は、dictionary.ContainsKey(d2)と評価される必要がありtrueます。

これを実現するために、新しいオブジェクトを作成しclass ComparableDictionary : SortedDictionary<long, string>、次のものを含めました。

public override int GetHashCode() {            
   StringBuilder str = new StringBuilder();
   foreach (var item in this) {
      str.Append(item.Key);
      str.Append("_");
      str.Append(item.Value);
      str.Append("%%");
   }
   return str.ToString().GetHashCode();
 }

私の単体テストでは、これは等価性とハッシュコードの両方の基準を満たしています。ただし、GetHashCode のガイドラインとルールを読んでいると、次のことに気付きました。

規則: GetHashCode によって返される整数は、オブジェクトがハッシュ コードが安定していることに依存するデータ構造に含まれている間、決して変更してはなりません。

危険ではありますが、オブジェクトのフィールドが変化するにつれてハッシュ コード値が変化する可能性があるオブジェクトを作成することは許容されます。そのようなオブジェクトがあり、それをハッシュテーブルに入れる場合、オブジェクトを変更するコードとハッシュテーブルを維持するコードには、オブジェクトが存在している間に変更されないことを保証する合意されたプロトコルが必要です。ハッシュテーブル。そのプロトコルがどのように見えるかはあなた次第です。

オブジェクトのハッシュ コードがハッシュ テーブル内にある間に変化する可能性がある場合、明らかに、Contains メソッドは機能しなくなります。オブジェクトをバケット #5 に入れ、それを変更します。セットに変更されたオブジェクトが含まれているかどうかを尋ねると、セットはバケット #74 を探しますが、見つかりません。

オブジェクトは、予期しない方法でハッシュ テーブルに配置される可能性があることを覚えておいてください。多くの LINQ シーケンス演算子は、ハッシュ テーブルを内部的に使用します。オブジェクトを返す LINQ クエリを列挙しているときに、危険なほどオブジェクトを変更しないでください。

現在、 は、すべてのコレクションDictionary<ComparableDictionary, List<String>>の内容を設定する必要がある場所で、コード内で 1 回だけ使用されます。ComparableDictionaryしたがって、これらのガイドラインによれば、私が行ったように (完全に辞書の内容に基づいて)オーバーライドすることは許容されると思います。GetHashCode

その紹介の後、私の質問は次のとおりです。

  1. SortedDictionaryに比べてのパフォーマンスが非常に悪いことはわかっていますDictionary(そして、何百ものオブジェクトのインスタンス化を行うことができます)。使用する唯一の理由SortedDictionaryは、挿入の順序に関係なく、辞書の内容に基づいて等価比較を機能させるためです。を使用せずにこの平等要件を達成するためのより良い方法はありSortedDictionaryますか?
  2. の実装はGetHashCode要件に基づいて受け入れられますか? 変更可能なコンテンツに基づいていますが、それが使用されている場所はコンテンツが設定された後 (だと思います) だけなので、それはリスクをもたらすべきではないと思います。

注Dictionary:またはを使用してこれらを設定している間SortedDictionary、私はこれらのコレクション型に執着していません。主な必要性は、値のペアを格納できるコレクションであり、上記で定義された等価性とハッシュの要件を満たします。

4

1 に答える 1

6

あなたのGetHashCode実装は私には受け入れられるように見えますが、それは私のやり方ではありません。

これは私がすることです：

  • 継承ではなく合成を使用します。他のことは別として、継承は平等の点で奇妙になります
  • Dictionary<TKey, TValue>辞書内で変数を使用する
  • GetHashCode個々のキーと値のペアのハッシュ コードの XOR を取得して実装する
  • サイズが同じかどうかをチェックして等価性を実装し、次に「this」のすべてのキーをチェックして、その値が他の辞書で同じかどうかを確認します。

だから、このようなもの：

public sealed class EquatableDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>, IEquatable<ComparableDictionary<TKey, TValue>>
{
    private readonly Dictionary<TKey, TValue> dictionary;

    public override bool Equals(object other)
    {
        return Equals(other as ComparableDictionary<TKey, TValue>);
    }

    public bool Equals(ComparableDictionary<TKey, TValue> other)
    {
        if (ReferenceEquals(other, null))
        {
            return false;
        }
        if (Count != other.Count)
        {
            return false;
        }
        foreach (var pair in this)
        {
            var otherValue;
            if (!other.TryGetValue(pair.Key, out otherValue))
            {
                return false;
            }
            if (!EqualityComparer<TValue>.Default.Equals(pair.Value,
                                                         otherValue))
            {
                return false;
            }
        }
        return true;
    }

    public override int GetHashCode()
    {
        int hash = 0;
        foreach (var pair in this)
        {
            int miniHash = 17;
            miniHash = miniHash * 31 + 
                   EqualityComparer<TKey>.Default.GetHashCode(pair.Key);
            miniHash = miniHash * 31 + 
                   EqualityComparer<Value>.Default.GetHashCode(pair.Value);
            hash ^= miniHash;
        }
        return hash;
    }

    // Implementation of IDictionary<,> which just delegates to the dictionary
}

また、null 値に対応しているかどうかを思い出せないことにも注意してくださいEqualityComparer<T>.Default.GetHashCode。null の場合は 0 を返す疑いがあります。ただし、チェックする価値があります:)

于 2011-05-29T14:32:29.253 に答える