Best way to compare two Dictionary for equality

问题:

Is this the best way to create a comparer for the equality of two dictionaries? This needs to be exact. Note that Entity.Columns is a dictionary of 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(); 
    }
}

Also not too sure about the GetHashCode implementation.

Thanks!

回答1:

Here's what I would do:

    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;
    }

That way you don't need to order the entries (which is a O(n log n) operation) : you only need to enumerate the entries in the first dictionary (O(n)) and try to retrieve values by key in the second dictionary (O(1)), so the overall complexity is O(n).

Also, note that your GetHashCode method is incorrect: in most cases it will return different values for different dictionary instances, even if they have the same content. And if the hashcode is different, Equals will never be called... You have several options to implement it correctly, none of them ideal:

• build the hashcode from the content of the dictionary: would be the best option, but it's slow, and GetHashCode needs to be fast
• always return the same value, that way Equals will always be called: very bad if you want to use this comparer in a hashtable/dictionary/hashset, because all instances will fall in the same bucket, resulting in O(n) access instead of O(1)
• return the Count of the dictionary (as suggested by digEmAll): it won't give a great distribution, but still better than always returning the same value, and it satisfies the constraint for GetHashCode (i.e. objects that are considered equal should have the same hashcode; two "equal" dictionaries have the same number of items, so it works)

回答2:

Something like this comes to mind, but there might be something more efficient:

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]));
}

回答3:

It seems good to me, perhaps not the fastest but working.

You just need to change the GetHashCode implementation that is wrong.

For example you could return obj.Columns.Count.GetHashCode()