两个元素构成的元组的列表或字典

Question

我有一组由两个字符串键值对组成的集合 { (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]]或其他方法？如果使用Dictionary，是否有任何方法告诉它将(K1,K2)视为(K2,K1)，以便我不必添加两个组合？或者也许添加(K1,K2)和(K2,K1)是正确的方法？

谢谢。

- pbz

---

显然我无法输入lt或gt字符，它们不会被转义，所以我用括号代替了它们。 - pbz

你需要对这个集合做什么？比如说，你想要怎样查找值？ - Jon Skeet

@JonSkeet 我只需要快速检查(a1, b1)和(b1, a1)是否已经在集合中。我正在处理大量这些事情，所以它需要很快。谢谢。 - pbz

Answer 1

制作一个自定义类来实现IEquatable接口（并确保正确覆盖GetHashCode方法）。然后您可以在HashSet<T>中使用它，这样两个对可自动变得“相等”。

- Reed Copsey

---

那样就可以正确地“索引”项目了吗？我试图防止“扫描”，即为每个项目检查调用“equals”。 - pbz

只要您有一个明智的哈希码，那就没问题。 - Jon Skeet

GetHashCode应该长什么样子？key1+key2还是key2+key1？ - pbz

@pbz并不重要，只要<a,b>和<b,a>产生完全相同的哈希码。一个简单的加法或XOR都可以实现这个目的... - Reed Copsey

这可能很基础，但我显然漏掉了什么。你能给我一个例子吗？其中一个("abc", "def")的哈希值与另一个("def", "abc")的哈希值相同。谢谢。 - pbz

@pbz 你可以直接使用 return str1.GetHashCode() ^ str2.GetHashCode(); - Reed Copsey

Answer 2

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

1. 定义类 Key，定义相等和哈希运算符以及方法（这意味着您需要定义方法 Equals，运算符 ==，方法 GetHashCode，如果编译器需要其他方法，则还需定义）。
2. 使用 HashSet<Key>。

- Al Kepp

---

不，这不是一个作业问题...我只是试图以非模糊的方式解释。 - pbz

但是如果我重写Equals方法，那么这是否会减慢在列表中查找项目的速度？这是否有违快速访问的目的？谢谢。 - pbz

我们几乎谈不上减速 - 因为你只需要一种比较两个键的方法。如果你没有提供比较键的方法，它就无法工作。 - Al Kepp

Answer 3

我会使用一个字典，其中键是由一个函数生成的，该函数接受2个字符串并生成哈希值，方法如下：比较两个字符串，构建一个由“较小”的字符串+分隔符+“较大”的字符串组成的连接字符串，这样顺序就不重要了。类似的“equals”运算符也可以实现。

- omer schleifer

---

是的，使用 String.Compare(str1, str2)。 - omer schleifer

Answer 4

创建一个存储类，公开Add（a，b）和类似函数。内部存储可以是一个HashSet<T>，其中T是一个合适的字符串元组键。关于此键和比较器的唯一重要之处是使用对称的哈希和相等函数，即（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;
          }
       }
   }

}

- Anders Forsgren

---

一种老习惯是总是将哈希值组合起来，例如"a*prime_number + b"。这是通常的简单模式，用于组合哈希码以避免冲突，但现在我实际上不确定在进行对称哈希时是否严格需要它。如果我只对哈希值求和，可能会在a、b之间创建不对称性。也许有人可以在这里填补一下，现在已经很晚了... - Anders Forsgren

当aHash和bHash是哈希值时，为什么不直接将它们进行异或运算？那样会有问题吗？ - Al Kepp

如果经常添加相等字符串的元组，会很糟糕，因为所有这样的元组都会得到相同的哈希值（零）。 - Anders Forsgren