5

文字列の2つのキーのペアのセット{（a1、b1）、（a2、b2）、（a3、b3）、...}があります。私のシナリオ（a1、b1）==（b1、a1）では、（a1、b1）または（b1、a1）の組み合わせを1回だけセットに含める必要があります。

C＃アプリケーションでは、次のことができる必要があります。

  • これらの（a、b）タプルの新しいペアを追加します
  • （a1、b1）または（b1、a1）のペアがすでに私のテーブルにあるかどうかを効率的に（つまり高速に）チェックします。

Dictionary [Tuple [K1、K2]]などを使用して、このようなものをどのように実装しますか？辞書を使用している場合、（K1、K2）を（K2、K1）と同じと見なすように指示する方法はありますか？両方の組み合わせを追加する必要はありませんか？または、（K1、K2）と（K2、K1）の両方を追加するのが良い方法ですか？

ありがとう。

4

4 に答える 4

6

IEquatableを実装するカスタムクラスを作成します（適切にオーバーライドするようにしてくださいGetHashCode）。次に、これをで使用できHashSet<T>、2つのペアを自動的に「等しく」することができます。

于 2013-03-24T19:31:02.907 に答える
2

これは宿題ですか？それは本からの問題のように見えます。

  1. クラスKeyを定義し、等式とハッシュの演算子とメソッドを定義します。Equals（つまり、メソッド、演算子==、メソッドGetHashCode、およびコンパイラが必要とする場合は他のメソッドを定義する必要があります。）
  2. を使用しHashSet<Key>ます。
于 2013-03-24T19:27:46.280 に答える
2

2つの文字列を受け入れ、次のようなハッシュを生成する関数によってキーが生成される辞書を使用します。両方の文字列を比較し、「小さい」文字列+区切り文字+「大きい」文字列で構成される連結文字列を作成します。このように順序は重要ではありません。同様の「等しい」演算子も実装できます。

于 2013-03-24T19:33:38.860 に答える
2

Add（a、b）および同様の関数を公開するストレージクラスを作成します。内部ストレージはHashSet<T>、Tが適切な文字列タプルキーである場合があります。このキーと比較器で重要なのは、対称的なハッシュ関数と等式関数を使用することだけです。つまり、（a、b）は（b、a）に等しく、その結果、hash（a、b）== hash（b、a ）。

前に指摘したように、多くのハッシュ関数にはこのプロパティがあります。たとえば、ハッシュ値の合計やxorなどです。xorを使用しないことを選択したのは、等しい文字列のすべてのペアがハッシュゼロを持つことを意味し、等しい文字列のペアが発生する可能性がある場合、ルックアップが非効率になる可能性があるためです。

以下の実装では、すべての文字列がnull以外であると想定していますが、エラーチェックはありません。

public class Storage
{
   private HashSet<Key> set;

   public Storage()
   {
      set = new HashSet<Key>(new Key.Comparer());
   }

   public void Add(string a, string b)
   {
      set.Add(new Key{A=a, B=b});
   }

   public bool Contains(string a, string b)
   {
      return set.Contains(new Key{A=a, B=b});
   }

   internal class Key
   {
       internal String A { get; set; }
       internal String B { get; set; }
       internal class Comparer : IEqualityComparer<Key>
       {
          public bool Equals(Key x, Key y)
          {
             return (x.A == y.A && x.B == y.B) || (x.A == y.B && x.B == y.A);
          }
          public int GetHashCode(Key k)
          {
             int aHash = k.A.GetHashCode();
             int bHash = k.B.GetHashCode();
             // Hash for (x,y) same as hash for (y,x)
             if (aHash > bHash)
                return bHash * 37 + aHash;
             return aHash * 37 + bHash;
          }
       }
   }

}
于 2013-03-24T19:47:16.370 に答える