无论插入顺序如何,等效内容相等的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类型用作另一个的键Dictionary,如果HashCodes不基于相同的内容进行评估,则使用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();
 }

在我的单元测试中,这符合相等和哈希码的标准.但是,在阅读GetHashCode的指南和规则时,我遇到了以下内容:

规则:当对象包含在依赖于哈希代码保持稳定的数据结构中时,GetHashCode返回的整数必须永远不会更改

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

如果对象的哈希代码在哈希表中变异,那么显然Contains方法就会停止工作.你把对象放在#5桶中,你改变它,当你问集合是否包含变异对象时,它会在#74桶中查找并找不到它.

请记住,对象可以以您不期望的方式放入哈希表中.许多LINQ序列运算符在内部使用哈希表.在枚举返回它们的LINQ查询时,不要危险地改变对象!

现在,Dictionary<ComparableDictionary, List<String>>它只在代码中使用一次,在一个ComparableDictionary应该设置所有集合的内容的地方.因此,根据这些指导原则,我认为GetHashCode按照我的方式覆盖(完全基于字典的内容)是可以接受的.

在介绍之后,我的问题是:

1. 我知道SortedDictionary与Dictionary(和我可以有数百个对象实例化)相比,性能非常差.使用的唯一原因SortedDictionary是,无论插入顺序如何,我都可以根据字典的内容进行相等比较.是否有更好的方法来实现这种平等要求而不必使用SortedDictionary？
2. 我的实施是否GetHashCode符合要求？虽然它是基于可变内容,但我不认为这会带来任何风险,因为它使用的唯一地方(我认为)是在内容设置之后.

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

Answer 1

你的GetHashCode实现对我来说是可以接受的,但我不是这样做的.

这就是我要做的:

• 使用组合而不是继承.除了其他任何东西,继承在平等方面变得奇怪
• Dictionary<TKey, TValue>在字典中使用变量
• GetHashCode通过对各个键/值对哈希码进行XOR来实现
• 通过检查大小是否相同来实现相等性,然后检查"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表示null.值得检查:)