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

我有一组双键字符串{（a1，b1），（a2，b2），（a3，b3），...}。在我的场景（a1，b1）==（b1，a1）中，所以a（a1，b1）或（b1，a1）组合应该只是我的集合的一部分。两个关键元组的列表或字典

在C＃应用程序，我需要能够：

添加的这些新的对（A，B）元组
高效（即快速）检查，如果一对（A1，B1 ）或（b1，a1）已经在我的表格中。

你将如何实现这样的事情，用字典[Tuple [K1，K2]]或其他？如果使用字典，有什么办法可以让它考虑（K1，K2）与（K2，K1）相同，所以我不必添加这两种组合？或者可能加入（K1，K2）和（K2，K1）是要走的路？

谢谢。

来源

2013-03-24 pbz

显然我不能键入LT或GT的人物，他们没有得到逃脱，所以我代替那些括号/圆括号 – pbz 2013-03-24 19:27:25

你有什么需要用一套呢？例如，您想如何查看价值？ – 2013-03-24 19:28:13

@JonSkeet我只需要快速检查（a1，b1）和（b1，a1）是否已经在集合中。我正在处理大量的这些事情，所以它需要很快。谢谢。 – pbz 2013-03-24 19:29:51

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

正如前面指出的，许多散列函数都有这个属性，例如散列值的和和。我选择不使用xor，因为它意味着所有的对等字符串都会有散列零，如果可能的话，可能会导致低效率的查找。

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

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-24 19:47:16

为什么使用* 37？ – pbz 2013-03-24 19:50:57

一种总是将哈希合并为“a * prime_number + b”的旧习惯。当组合哈希代码以避免冲突时，这是通常的简单模式，但我现在实际上并不确定在做这样的对称散列时它是否是严格必要的，现在我想到了它。它可能会造成a，b之间的不对称，如果我只将哈希值相加，那么它就不会存在。有人可以在这里填写，其后期... – 2013-03-24 19:56:25

当aHash和bHash是哈希值时，为什么不简单地将它们异或？那会不好？ – 2013-03-24 23:20:32

这是功课吗？这看起来像是一本书的问题。

定义类Key定义了相等和散列运算符和方法。（这意味着你应该定义方法Equals，运算符==，方法GetHashCode，如果编译器需要它们可能还有其他方法）。
使用HashSet<Key>。

来源

2013-03-24 19:27:46

不，不是一个家庭作业问题......我只是试图以非模糊的方式解释。 – pbz 2013-03-24 19:28:42

但是，如果我重写Equals方法，是不是减慢了在列表中找到项目的速度？这是否不符合快速访问的目的？谢谢。 – pbz 2013-03-24 19:32:00

我们几乎不可能在这里谈论减速 - 因为您只需要一种方法来比较两个键。如果您没有提供比较密钥的方法，则无法使用。 – 2013-03-24 23:19:17

制作一个自定义类，实现IEquatable（并确保正确覆盖GetHashCode）。然后，您可以在HashSet<T>中使用它，并且这两对可以自动“平等”。

来源

2013-03-24 19:31:02

而且这将正确地“索引”项目？我试图阻止“扫描”，即为每个项目检查调用“等于”。 – pbz 2013-03-24 19:33:20

@pbz：只要你有一个明智的哈希码，那应该没问题。 – 2013-03-24 19:34:45

GetHashCode应该是什么样子？ key1 + key2或key2 + key1？ – pbz 2013-03-24 19:34:55

我会使用一个字典，其中的密钥由接受2个字符串的函数生成，并像这样生成哈希：比较两个字符串，构建一个由“较小”字符串+分隔符+“较大”串。这种顺序无关紧要。一个类似的“等于”操作符也可以被实现。

来源

2013-03-24 19:33:38

小于string1 pbz 2013-03-24 19:42:50

是的，使用String.Compare（str1，str2） – 2013-03-24 19:51:59

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

回答

相关问题