比较两个Dictionary<T>是否相等的最佳方法

Question

这是创建用于比较两个字典相等性的最佳方法吗？请注意，Entity.Columns是一个KeyValuePair(string, object)类型的字典：

public class EntityColumnCompare : IEqualityComparer<Entity>
{
    public bool Equals(Entity a, Entity b)
    {
        var aCol = a.Columns.OrderBy(KeyValuePair => KeyValuePair.Key);
        var bCol = b.Columns.OrderBy(KeyValuePAir => KeyValuePAir.Key); 

        if (aCol.SequenceEqual(bCol))
            return true;
        else
            return false;           
    }

    public int GetHashCode(Entity obj)
    {
        return obj.Columns.GetHashCode(); 
    }
}

我对 GetHashCode 实现也不太确定。

谢谢！

- Sean Thoman

---

请查看此问题 - https://dev59.com/jHVD5IYBdhLWcg3wNY1Z - Stuart

GetHashCode是错误的。我会说在不知道字典大小的情况下返回obj.Columns.Count。 - Hans Passant

Answer 1

这是我会做的：

    public bool Equals(Entity a, Entity b)
    {
        if (a.Columns.Count != b.Columns.Count)
            return false; // Different number of items

        foreach(var kvp in a.Columns)
        {
            object bValue;
            if (!b.Columns.TryGetValue(kvp.Key, out bValue))
                return false; // key missing in b
            if (!Equals(kvp.Value, bValue))
                return false; // value is different
        }
        return true;
    }

这样你就不需要对条目进行排序（这是一个 O(n log n) 的操作）：你只需要枚举第一个字典中的条目(O(n))，并尝试在第二个字典中按键检索值(O(1))，因此总体复杂度为O(n)。

此外，请注意您的GetHashCode方法是不正确的：在大多数情况下，即使它们具有相同的内容，它也会为不同的字典实例返回不同的值。如果哈希码不同，则永远不会调用Equals...您有几种选项可以正确实现它，但没有一种是理想的：

- 从字典的内容构建哈希码：这将是最好的选择，但速度较慢，并且GetHashCode需要快速执行。 - 总是返回相同的值，这样Equals将始终被调用：如果您想在散列表/字典/哈希集中使用此比较器，那么非常糟糕，因为所有实例都将落入同一个桶中，导致O(n)访问而不是O(1)。 - 返回字典的Count（如digEmAll所建议的）：它不会给出很好的分布，但仍然比总是返回相同的值要好，并且它满足GetHashCode的约束（即被认为相等的对象应具有相同的哈希码；两个“相等”的字典具有相同数量的项，因此可以工作）。

- Thomas Levesque

---

实际上，我认为在字典或列表的GetHashCode()实现中，我们无法做更多的事情。可以使用前n个元素计算哈希值，从而改善分布，每个桶平均变小n倍，但也会将GetHashCode的复杂度增加n倍。因此基本上没有优势... - digEmAll

@digEmAll，不要那么快就放弃那个想法...我没有算过，但我认为它可能会起作用。 - Thomas Levesque

当然，我只是粗略地计算了一下，但我认为这是相当正确的...顺便说一句，这个参数可能值得提出一个问题 :) - digEmAll

如果您控制字典中所有更改的另一种方法是保持累积更新的哈希码。例如，您可以保留四个int，其中包含字典中所有键和值的哈希码的总和和'xor'。字典的GetHashCode将返回这四个int值的混合。 - supercat

Answer 2

我想到的是这样的内容，但可能还有更高效的方式：

public static bool Equals<TKey, TValue>(IDictionary<TKey, TValue> x, 
    IDictionary<TKey, TValue> y)
{
    return x.Keys.Intersect(y.Keys).Count == x.Keys.Count &&
        x.Keys.All(key => Object.Equals(x[key], y[key]));
}

- Richard Szalay

---

当x是y的子集时，返回true。 - Nuri Tasdemir

Answer 3

对我来说，它看起来不错，也许不是最快的，但是能够工作。

你只需要更改错误的GetHashCode实现即可。

例如，你可以返回obj.Columns.Count.GetHashCode()

- digEmAll

---

@Sean：实际上，它完全相同，事实上int.GetHashCode()的实现是：returns this;。你可以保留GetHashCode()，因为在我看来这样更符合风格，而且可能JIT编译器会内联代码，从而节省对GetHashCode()的调用 :) - digEmAll