5

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

在 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）。然后您可以在 a 中使用它HashSet<T>，并且可以自动使两对“相等”。

于 2013-03-24T19:31:02.907 回答
2

这是作业吗？这看起来像是一本书的问题。

  1. 定义类Key，定义相等和哈希运算符和方法。（这意味着您应该定义 method Equals、 operator ==、 methodGetHashCode以及可能的其他方法，如果编译器需要的话。）
  2. 使用HashSet<Key>.
于 2013-03-24T19:27:46.280 回答
2

我会使用一个字典，其中键是由一个函数生成的，该函数接受 2 个字符串并生成这样的哈希：比较两个字符串，构建一个由“较小”字符串 + 分隔符 +“较大”字符串组成的连接字符串。这种方式顺序无关紧要。也可以实现类似的“等于”运算符。

于 2013-03-24T19:33:38.860 回答
2

创建一个公开 Add(a, b) 和类似函数的存储类。内部存储可以是HashSet<T>其中 T 是合适的字符串元组键。这个 Key 和 comparer 唯一重要的是使用对称的哈希和相等函数，即 (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;
          }
       }
   }

}
于 2013-03-24T19:47:16.370 回答