CODEWITHSUNDEEP
c#dictionaryequality
rony l
rony l

Reputation: 6002

Testing for equality between dictionaries in C#

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

Upvotes: 86

Views: 57185

Answers (8)

Adithya Upadhya
Adithya Upadhya

Reputation: 2375

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.

Upvotes: 3

Jason Masters
Jason Masters

Reputation: 309

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

Upvotes: 2

Machtyn
Machtyn

Reputation: 3272

I thought the accepted answer would be correct based on what I was reading in the smarthelp for the Except method: "Produces the set difference of two sequences by using the default equality comparer to compare values." But I discovered it is not a good answer.

Consider this code:

Dictionary<string, List<string>> oldDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}},
     {"003C", new List<string> {"Doe", "Jane"}}};
Dictionary<string, List<string>> newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}},
     {"003C", new List<string> {"Doe", "Jane"}}};

bool equal = oldDict.Count.Equals(newDict.Count) && !oldDict.Except(newDict).Any();
Console.WriteLine(string.Format("oldDict {0} newDict", equal?"equals":"does not equal"));
equal = oldDict.SequenceEqual(newDict);
Console.WriteLine(string.Format("oldDict {0} newDict", equal ? "equals" : "does not equal"));

Console.WriteLine(string.Format("[{0}]", string.Join(", ", 
    oldDict.Except(newDict).Select(k => 
        string.Format("{0}=[{1}]", k.Key, string.Join(", ", k.Value))))));

This results in the following:

oldDict does not equal newDict
oldDict does not equal newDict
[001A=[John, Doe], 002B=[Frank, Abignale], 003C=[Doe, Jane]]

As you can see, both "oldDict" and "newDict" are setup exactly the same. And neither the suggested solution nor a call to SequenceEqual works properly. I wonder if it is a result of the Except using lazy loading or the way the comparer is setup for the Dictionary. (Although, looking at the structure and reference explanations suggest it should.)

Here's the solution I came up with. Note that the rule I used is as follows: two dictionaries are equal if both contain the same keys and the values for each key match. Both keys and values must be in the same sequential order. And my solution may not be the most efficient, since it relies on iterating through the entire set of keys. 

private static bool DictionaryEqual(
    Dictionary<string, List<string>> oldDict, 
    Dictionary<string, List<string>> newDict)
{
    // Simple check, are the counts the same?
    if (!oldDict.Count.Equals(newDict.Count)) return false;

    // Verify the keys
    if (!oldDict.Keys.SequenceEqual(newDict.Keys)) return false;

    // Verify the values for each key
    foreach (string key in oldDict.Keys)
        if (!oldDict[key].SequenceEqual(newDict[key]))
            return false;

    return true;
}

Also see how the results change if: Key order is not the same. (returns false)

newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"003C", new List<string> {"Doe", "Jane"}},
     {"002B", new List<string> {"Frank", "Abignale"}}};

and Key order matches, but Value does not match (returns false)

newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}},
     {"003C", new List<string> {"Jane", "Doe"}}};

If sequence order does not matter, the function can be changed to the following, but there is likely a performance hit.

private static bool DictionaryEqual_NoSort(
    Dictionary<string, List<string>> oldDict,
    Dictionary<string, List<string>> newDict)
{
    // Simple check, are the counts the same?
    if (!oldDict.Count.Equals(newDict.Count)) return false;

    // iterate through all the keys in oldDict and
    // verify whether the key exists in the newDict
    foreach(string key in oldDict.Keys)
    {
        if (newDict.Keys.Contains(key))
        {
            // iterate through each value for the current key in oldDict and 
            // verify whether or not it exists for the current key in the newDict
            foreach(string value in oldDict[key])
                if (!newDict[key].Contains(value)) return false;
        }
        else { return false; }
    }

    return true;
}

Check out if the DictionaryEqual_NoSort using the following for newDict (DictionaryEquals_NoSort returns true):

newDict = new Dictionary<string, List<string>>()
    {{"001A", new List<string> {"John", "Doe"}},
     {"003C", new List<string> {"Jane", "Doe"}},
     {"002B", new List<string> {"Frank", "Abignale"}}};

Upvotes: 0

LukeH
LukeH

Reputation: 269298

It really depends on what you mean by equality.

This method will test that two dictionaries contain the same keys with the same values (assuming that both dictionaries use the same IEqualityComparer<TKey> implementation).

public bool CompareX<TKey, TValue>(
    Dictionary<TKey, TValue> dict1, Dictionary<TKey, TValue> dict2)
{
    if (dict1 == dict2) return true;
    if ((dict1 == null) || (dict2 == null)) return false;
    if (dict1.Count != dict2.Count) return false;

    var valueComparer = EqualityComparer<TValue>.Default;

    foreach (var kvp in dict1)
    {
        TValue value2;
        if (!dict2.TryGetValue(kvp.Key, out value2)) return false;
        if (!valueComparer.Equals(kvp.Value, value2)) return false;
    }
    return true;
}

Upvotes: 16

supercat
supercat

Reputation: 81105

If two dictionaries contain the same keys, but in different order, should they be considered equal? If not, then the dictionaries should be compared by running enumerators through both simultaneously. This will probably be faster than enumerating through one dictionary and looking up each element in the other. If you have advance knowledge that equal dictionaries will have their elements in the same order, such a double-enumeration is probably the way to go.

Upvotes: -1

Nick Jones
Nick Jones

Reputation: 6493

dic1.Count == dic2.Count && !dic1.Except(dic2).Any();

Upvotes: 140

abatishchev
abatishchev

Reputation: 100248

@Allen's answer:

bool equals = a.Intersect(b).Count() == a.Union(b).Count()

is about arrays but as far as IEnumerable<T> methods are used, it can be used for Dictionary<K,V> too.

Upvotes: 1

Lee
Lee

Reputation: 144126

You could use linq for the key/value comparisons:

public bool Compare<TKey, TValue>(Dictionary<TKey, TValue> dict1, Dictionary<TKey, TValue dict2)
{
    IEqualityComparer<TValue> valueComparer = EqualityComparer<TValue>.Default;

    return  dict1.Count == dict2.Count &&
            dict1.Keys.All(key => dict2.ContainsKey(key) && valueComparer.Equals(dict1[key], dict2[key]));
}

Upvotes: 7

Related Questions