SortedDictionary<TKey，TValue>：检查内容是否等于另一个SortedDictionary？

Question

我想知道:如果我有两个SortedDictionary对象，那么找出它们的内容是否相同的最快方法是什么？循环所有键并检查值听起来不是最好的解决方案。仅仅检查GetHashCode()就足够了吗？

编辑:我已经尝试了一些。请参阅以下代码：

SortedDictionary<string, string> o1 = new SortedDictionary<string, string>( );
SortedDictionary<string, string> o2 = new SortedDictionary<string, string>( );
o1["k1"] = "v1";
o1["k2"] = "v2";
o1["k3"] = "v3";

o2["k2"] = "v2";
o2["k1"] = "v1";
o2["k3"] = "v3";

Console.WriteLine( "o1:" );
foreach ( KeyValuePair<string, string> oKeyValuePair in o1 )
{
    Console.WriteLine( oKeyValuePair.GetHashCode( ) );
}
Console.WriteLine( "o2:" );
foreach ( KeyValuePair<string, string> oKeyValuePair in o2 )
{
    Console.WriteLine( oKeyValuePair.GetHashCode( ) );
}
Console.ReadKey( );

对于两个排序的字典，各个键值对的散列代码是相同的，即使值被添加的顺序不同。这很好。所以我遗漏了一个步骤:如何从所有的哈希码中获得一个唯一的哈希码？

Answer 1

您必须准备好遍历它们，但您可以首先测试一些重要的捷径。

第一个捷径，是检查对象的身份。虽然"A is A“并不像Ayn Rand认为的那么深刻，但它是一种让相等代码更快的便捷方法。同一性总是需要相等，在真实的代码中，最终将某些东西与自身进行比较是很常见的(特别是在集合查找、循环以及对象通过多层代码传递的地方)。

另一种是，如果内容相同，则大小不能不同，并且大小很容易获得。

因此，你能得到的最快速度是：

public static bool EqualSortedDict<K, V>(SortedDictionary<K, V> x, SortedDictionary<K, V> y)
{
  if(ReferenceEquals(x, y))
    return true;
  if(ReferenceEquals(x, null) || ReferenceEquals(y, null))
    return false; //both being null already hit above.
  if(x.Count != y.Count)
    return false;
  if(!x.Comparer.Equals(y.Comparer))
    return false;//check if this is what you need. Probably is but might
                 //not be in some cases.
  foreach(KeyValuePair<K, V> kvp in x)
  {
    V cmpValue = default(V);
    if(!y.TryGetValue(kvp.Key, out cmpValue) || !kvp.Value.Equals(cmpValue))
      return false;
  }
  return true;
}

请注意，上面GetHashCode()不起作用的原因是SortedDictionary上的GetHashCode()的默认实现只在对象标识上起作用。如果您需要一个基于值的GetHashCode() (如果您的SortedDictionary本身将是一个键或放在一个HashSet中)，那么您将必须实现一个生成适当散列代码的IEqualityComparer。即使到那时，它也会花费很长的时间来计算(它可能总是循环所有的项来做你想做的事情)，虽然a.GetHashCode() != b.GetHashCode()证明a != b(对于哈希码支持的相等的定义)，a.GetHashCode() == b.GetHashCode()并不能证明a == b，因为会有冲突。

Answer 2

不，即使SortedDictionary<,>覆盖了GetHashCode，检查它也是不够的--我不相信它会这样做。

据我所知，您必须循环检查所有键和值。从根本上说，这是任何解决方案都必须要做的事情。您还应该检查所涉及的比较函数是否也相同……否则，这些字典就不是真正的等价物。