c# - Dictionary 的实现，其中等效内容相等并返回相同的哈希码，而不管插入顺序如何

Question

我需要使用 Dictionary<long, string>给出两个实例的集合 d1和 d2他们每个人都有相同的 KeyValuePair<long, string>内容，可以按任何顺序插入:

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

使用 SortedDictionary 最容易实现第一个要求。而不是常规的 Dictionary .

第二个要求是必要的，因为我有一点需要存储 Dictionary<Dictionary<long, string>, List<string> - 主Dictionary type 用作另一个 Dictionary 的键, 如果哈希码不基于相同的内容进行评估，则使用 ContainsKey()不会按照我想要的方式工作(即:如果已经有一个项目插入到字典中，并以 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();
 }

在我的单元测试中，这符合相等性和哈希码的标准。但是，在阅读Guidelines and Rules for GetHashCode ，我遇到了以下情况:

Rule: the integer returned by GetHashCode must never change while the object is contained in a data structure that depends on the hash code remaining stable

It is permissible, though dangerous, to make an object whose hash code value can mutate as the fields of the object mutate. If you have such an object and you put it in a hash table then the code which mutates the object and the code which maintains the hash table are required to have some agreed-upon protocol that ensures that the object is not mutated while it is in the hash table. What that protocol looks like is up to you.

If an object's hash code can mutate while it is in the hash table then clearly the Contains method stops working. You put the object in bucket #5, you mutate it, and when you ask the set whether it contains the mutated object, it looks in bucket #74 and doesn't find it.

Remember, objects can be put into hash tables in ways that you didn't expect. A lot of the LINQ sequence operators use hash tables internally. Don't go dangerously mutating objects while enumerating a LINQ query that returns them!

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

介绍之后我的问题是:

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

注意:虽然我一直在使用 Dictionary 设置它们或 SortedDictionary ，我不拘泥于这些集合类型。主要需求是一个可以存储成对值并满足上面定义的相等性和散列要求的集合。

Answer 1

你的 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。不过值得一试:)