6

我需要使用Dictionary<long, string>给定两个实例的集合，d1并且d2它们每个都具有相同的KeyValuePair<long, string>内容，可以按任何顺序插入：

  1. (d1 == d2)评估为true
  2. d1.GetHashCode()==d2.GetHashCode()

通过使用 aSortedDictionary而不是常规的 ，最容易实现第一个要求Dictionary。

第二个要求是必要的，因为我有一个需要存储Dictionary<Dictionary<long, string>, List<string>的点 - 主要Dictionary类型用作另一个的键Dictionary，如果 HashCodes 不基于相同的内容进行评估，则 usingContainsKey()将无法按我想要的方式工作（即：如果已经有一个项目插入到字典中，d1作为它的键，那么dictionary.ContainsKey(d2)应该评估为true.

为此，我创建了一个新对象class ComparableDictionary : SortedDictionary<long, string>，并包含以下内容：

public override int GetHashCode() {            
   StringBuilder str = new StringBuilder();
   foreach (var item in this) {
      str.Append(item.Key);
      str.Append("_");
      str.Append(item.Value);
      str.Append("%%");
   }
   return str.ToString().GetHashCode();
 }

在我的单元测试中，这符合相等和哈希码的标准。但是，在阅读GetHashCode 的指南和规则时，我遇到了以下问题：

规则：当对象包含在依赖于哈希码保持稳定的数据结构中时，GetHashCode 返回的整数永远不能改变

虽然很危险，但允许对象的哈希码值随着对象的字段发生变异而发生变异是允许的。如果你有这样一个对象并且你把它放在一个哈希表中，那么改变对象的代码和维护哈希表的代码需要有一些商定的协议，以确保对象在它存在时不会发生变异哈希表。该协议的外观取决于您。

如果对象的哈希码在哈希表中时可能会发生变异，那么显然 Contains 方法将停止工作。您将对象放入存储桶#5，对其进行变异，当您询问集合是否包含变异对象时，它在存储桶#74 中查找并没有找到它。

请记住，对象可以以您意想不到的方式放入哈希表中。许多 LINQ 序列运算符在内部使用哈希表。不要在枚举返回对象的 LINQ 查询时危险地改变对象！

现在，在代码中只使用一次，在一个应该设置Dictionary<ComparableDictionary, List<String>>所有集合的内容的地方。ComparableDictionary因此，根据这些准则，我认为像我所做的那样覆盖是可以接受的GetHashCode（完全基于字典的内容）。

在介绍之后，我的问题是：

  1. 我知道与（我可以有数百个对象实例化）SortedDictionary相比，它的性能非常差。Dictionary使用的唯一原因SortedDictionary是我可以根据字典的内容进行相等比较工作，而不管插入顺序如何。有没有更好的方法来实现这个平等要求而不必使用 a SortedDictionary？
  2. GetHashCode根据要求，我的实施是否可以接受？即使它基于可变内容，我认为这不会带来任何风险，因为它唯一使用的地方（我认为）是在设置内容之后。

注意：虽然我一直在使用Dictionaryor设置这些SortedDictionary，但我并不喜欢这些集合类型。主要需求是一个可以存储值对并满足上面定义的相等和散列要求的集合。

4

1 回答 1

6

您的GetHashCode实现看起来对我来说是可以接受的，但这不是我的做法。

这就是我要做的：

  • 使用组合而不是继承。抛开别的不说，继承在平等方面变得很奇怪
  • 在字典中使用Dictionary<TKey, TValue>变量
  • GetHashCode通过对单个键/值对哈希码进行异或来实现
  • 通过检查大小是否相同来实现相等，然后检查“this”中的每个键以查看其值在另一个字典中是否相同。

所以是这样的：

public sealed class EquatableDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>, IEquatable<ComparableDictionary<TKey, TValue>>
{
    private readonly Dictionary<TKey, TValue> dictionary;

    public override bool Equals(object other)
    {
        return Equals(other as ComparableDictionary<TKey, TValue>);
    }

    public bool Equals(ComparableDictionary<TKey, TValue> other)
    {
        if (ReferenceEquals(other, null))
        {
            return false;
        }
        if (Count != other.Count)
        {
            return false;
        }
        foreach (var pair in this)
        {
            var otherValue;
            if (!other.TryGetValue(pair.Key, out otherValue))
            {
                return false;
            }
            if (!EqualityComparer<TValue>.Default.Equals(pair.Value,
                                                         otherValue))
            {
                return false;
            }
        }
        return true;
    }

    public override int GetHashCode()
    {
        int hash = 0;
        foreach (var pair in this)
        {
            int miniHash = 17;
            miniHash = miniHash * 31 + 
                   EqualityComparer<TKey>.Default.GetHashCode(pair.Key);
            miniHash = miniHash * 31 + 
                   EqualityComparer<Value>.Default.GetHashCode(pair.Value);
            hash ^= miniHash;
        }
        return hash;
    }

    // Implementation of IDictionary<,> which just delegates to the dictionary
}

另请注意，我不记得是否EqualityComparer<T>.Default.GetHashCode处理空值 - 我怀疑它确实如此，返回 0 表示空值。值得检查:)

于 2011-05-29T14:32:29.253 回答