两个关键元组的列表或字典

Question

我有一组双键对的字符串{(a1,b1),(a2,b2),(a3,b3),...}.在我的场景(a1,b1)==(b1,a1)中,所以a(a1,b1)或(b1,a1)组合应该只是我的一部分.

在C#应用程序中,我需要能够:

• 添加一对新的这些(a,b)元组
• 有效地(即快速)检查一对(a1,b1)或(b1,a1)是否已经在我的表中.

你会如何使用Dictionary [Tuple [K1,K2]]或其他东西实现这样的东西？如果使用字典,有没有办法让它考虑(K1,K2)与(K2,K1)相同,所以我不必添加两种组合？或者可能添加(K1,K2)和(K2,K1)是要走的路？

谢谢.

Answer 1

创建一个实现IEquatable的自定义类(并确保正确覆盖GetHashCode).然后你可以在a中使用它HashSet<T>,并且两对可以自动地"相等".

Answer 2

创建一个公开 Add(a, b) 和类似函数的存储类。内部存储可以是一个HashSet<T>，其中 T 是合适的字符串元组键。关于这个 Key 和比较器唯一重要的是使用对称的哈希函数和相等函数，即 (a,b) 等于 (b,a)，因此 hash(a,b) == hash(b,a) ）。

如前所述，许多哈希函数都具有此属性，例如哈希值的求和和异或。我选择不使用异或，因为这意味着所有相等字符串对的哈希值都为零，如果可能存在相等字符串对，这可能会导致查找效率低下。

下面的实现假设所有字符串都非空，但没有错误检查。

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;
          }
       }
   }

}