Testing for equality between dictionaries in C#

user_16418 0
Viewed 43220

Assuming dictionary keys and values have their equals and hash methods implemented correctly, what is the most succinct and efficient way to test for equality of two dictionaries?

In this context, two dictionaries are said to be equal if they contain the same set of keys (order not important), and for every such key, they agree on the value.

Here are some ways I came up with (there are probably many more):

public bool Compare1<TKey, TValue>(
    Dictionary<TKey, TValue> dic1, 
    Dictionary<TKey,TValue> dic2)
{
    return dic1.OrderBy(x => x.Key).
        SequenceEqual(dic2.OrderBy(x => x.Key));
}

public bool Compare2<TKey, TValue>(
    Dictionary<TKey, TValue> dic1, 
    Dictionary<TKey, TValue> dic2)
{
    return (dic1.Count == dic2.Count && 
        dic1.Intersect(dic2).Count().
        Equals(dic1.Count));
}

public bool Compare3<TKey, TValue>(
    Dictionary<TKey, TValue> dic1, 
    Dictionary<TKey, TValue> dic2)
{
    return (dic1.Intersect(dic2).Count().
        Equals(dic1.Union(dic2).Count()));
}
dictionary equality c#
8 Answers

In addition to @Nick Jones answer, you're going to need to implement gethashcode in the same, order agnostic way. I would suggest something like this:

public override int GetHashCode()
{
        var hash = 13;
        var orderedKVPList = this.DictProp.OrderBy(kvp => kvp.Key);
        foreach (var kvp in orderedKVPList)
        {
                 hash = (hash * 7)  + kvp.Key.GetHashCode();
                 hash = (hash * 7)  + kvp.Value.GetHashCode();
        }
        return hash;
}
user_83338650

Simple O(N) time, O(1) space solution with null checks

The other solutions using Set operations Intersect, Union or Except are good but these require additional O(N) memory for the final resultant dictionary which is just used for counting elements.

Instead, use Linq Enumerable.All to check this. First validate the count of two dictionaries, next, iterate over all D1's Key Value pairs and check if they are equal to D2's Key Value pairs. Note: Linq does allocate memory for a collection iterator but it's invariant of the collection size - O(1) space. Amortized complexity for TryGetValue is O(1).

// KV is KeyValue pair      
var areDictsEqual = d1.Count == d2.Count && d1.All(
     (d1KV) => d2.TryGetValue(d1KV.Key, out var d2Value) && (
          d1KV.Value == d2Value ||
          d1KV.Value?.Equals(d2Value) == true)
);

  • Why d1KV.Value == d2Value? - this is to check if object references are equal. Also, if both are null, d1KV.Value == d2Value will evaluate to true.

  • Why d1Kv.Value?.Equals(d2Value) == true? - Value?. is for null safe check and .Equals is meant to test equality of two objects based on your object's Equals and HashCode methods.

You can tweak the equality checks as you like. I'm assuming the Dict Values are nullable type to make the solution more generic (eg: string, int?, float?). If it's non-nullable type, the checks could be simplified.

Final note: In C# dictionary, the Keys can't be null. But Values can be null. Docs for reference.

user_25149860
Related