Generic Dictionary Equality Comparer

Question

I created the below comparer to allow me to use a generic dictionary as a key to another generic dictionary.

My GetHashCode implementation creates a hash based on all keys and their values; but I suspect its distribution could be improved?

Also my Equals method returns true only if the two arguments have exactly the same keys, with each key having exactly the same values. However, potentially there's a more efficient approach to this comparison which I've neglected?

using System.Collections.Generic;
using System.Linq;

namespace MyCompany.Collections.Generic
{
    public class DictionaryEqualityComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
    {
        readonly IEqualityComparer<TKey> keyComparer;
        readonly IEqualityComparer<TValue> valueComparer;

        public DictionaryEqualityComparer(): this(null, null){}
        public DictionaryEqualityComparer(IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
        {
            this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
            this.valueComparer = valueComparer ?? EqualityComparer<TValue>.Default;
        }

        public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)
        {
            if (a == null || b == null) return (a == null && b == null);                //if either value is null return false, or true if both are null
            return a.Count == b.Count                                                   //unless they have the same number of items, the dictionaries do not match
                && a.Keys.Intersect(b.Keys, keyComparer).Count() == a.Count             //unless they have the same keys, the dictionaries do not match
                && a.Keys.Where(key => ValueEquals(a[key], b[key])).Count() == a.Count; //unless each keys' value is the same in both, the dictionaries do not match
        }

        public int GetHashCode(IDictionary<TKey, TValue> obj)
        {
            //I suspect there's a more efficient formula for even distribution, but this does the job for now
            long hashCode = obj.Count;
            foreach (var key in obj.Keys)
            {
                hashCode += (key?.GetHashCode() ?? 1000) + (obj[key]?.GetHashCode() ?? 0);
                hashCode %= int.MaxValue; //ensure we don't go outside the bounds of MinValue-MaxValue
            }
            return (int)hashCode; //safe conversion thanks to the above %
        }

        private bool ValueEquals(TValue x, TValue y)
        {
            return valueComparer.Equals(x, y);
        }

    }
}

Answer 1

You said you built this specifically so you can use dictionaries as keys in other dictionaries?

In that case, you've got a problem. Consider the following demonstration:

var keyA = new Dictionary<string, int> { ["a"] = 4 };
var keyB = new Dictionary<string, int> { ["a"] = 4 };

var comparer = new DictionaryEqualityComparer<string, int>();
var dict = new Dictionary<Dictionary<string, int>, int>(comparer);
dict[keyA] = 10;

keyA["b"] = 5;
var x = dict[keyA];    // KeyNotFoundException: different hash
var y = dict[keyB];    // KeyNotFoundException: same hash, but not equal to original key

After modifying keyA, its hash-code is different, so a key lookup will fail. So far so good - this seems to be what you intended.

However, a lookup with keyB will also fail. Its hash-code is the same as keyA's original hash-code, so that part of the lookup succeeds, but because of hash collisions dict needs to compare it with the original key... which fails because keyA no longer has the same content.

That's why, generally speaking, the hash-code of an object should never change during its lifetime.

---

Also, the idea behind a hash-code is to have a quick, cheap way to filter out objects that are obviously not equal. Inspecting every single key and value seems fairly heavy-handed.

As for what you want to achieve... I suspect that will require a custom dictionary implementation, because you'll need to retain the original content of each key for future comparisons. At that point, I'd start thinking about why I even wanted to do this in the first place - there's likely a better solution for the original problem.

Answer 2

Thanks to the feedback of Pieter and Anon (answer since removed), here's the revised version of the above, should it be useful to others, or warrant further comment.

using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Collections.Immutable;

namespace MyCompany.Collections.Generic
{
    public class ImmutableDictionaryEqualityComparer<TKey, TValue> : IEqualityComparer<IImmutableDictionary<TKey, TValue>>
    {
        readonly IEqualityComparer<TKey> keyComparer;
        readonly IEqualityComparer<TValue> valueComparer;

        public ImmutableDictionaryEqualityComparer() : this(null, null) { }
        public ImmutableDictionaryEqualityComparer(IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
        {
            this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
            this.valueComparer = valueComparer ?? EqualityComparer<TValue>.Default;
        }

        public bool Equals(IImmutableDictionary<TKey, TValue> x, IImmutableDictionary<TKey, TValue> y)
        {
            if (x == null || y == null) return (x == null && y == null); //treat null == null, null != nonNull
            return BothHaveTheSameNumberOfItems(x, y)
                && BothHaveIdenticalKeyValuePairs(x, y);
        }

        public int GetHashCode(IImmutableDictionary<TKey, TValue> obj)
        {
            //this is far from the most efficient formula for even distribution, but is good enough
            if (obj == null) return 0;
            long hashCode = obj.Count + 1;//if count is 0 ensure our hash code is different to when obj is null
            foreach (var key in obj.Keys)
            {
                hashCode += (key?.GetHashCode() ?? 1566083941) + (obj[key]?.GetHashCode() ?? 0); //assign a non-zero number to null keys (1566083941 used as an arbitrary number / also one which features often in other hashing algorithms) / treat null values as 0
                hashCode %= int.MaxValue; //ensure we don't go outside the bounds of MinValue - MaxValue
            }
            return (int)hashCode; //safe conversion thanks to the above %
        }

        private bool BothHaveTheSameNumberOfItems(IImmutableDictionary<TKey, TValue> x, IImmutableDictionary<TKey, TValue> y)
        {
            Debug.Assert(x != null);
            Debug.Assert(y != null);
            return x.Count == y.Count;
        }

        private bool BothHaveIdenticalKeyValuePairs(IImmutableDictionary<TKey, TValue> x, IImmutableDictionary<TKey, TValue> y)
        {

            Debug.Assert(x != null);
            Debug.Assert(y != null);
            Debug.Assert(x.Count == y.Count);
            return x.All(kvp => y.TryGetValue(kvp.Key, out var yValue) && ValueEquals(kvp.Value, yValue));
        }
        private bool ValueEquals(TValue x, TValue y)
        {
            return valueComparer.Equals(x, y);
        }

    }
}

Related Unit Test Class:

(I haven't been able to write a test for the scenario which Pieter pointed out, since that scenario is no longer possible given the new design).

using System.Collections.Generic;
using System.Collections.Immutable;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace MyCompany.Collections.Generic.Test
{
    [TestClass]
    public class ImmutableDictionaryEqualityComparerTest
    {
        [TestMethod()]
        public void MatchingItemsMatchTest()
        {
            var instance = new ImmutableDictionaryEqualityComparer<string, string>();
            var a = (new Dictionary<string, string>() { { "One", "A" }, { "Two", "B" } }).ToImmutableDictionary();
            var b = (new Dictionary<string, string>() { { "Two", "B" }, { "One", "A" } }).ToImmutableDictionary(); //order doesn't matter
            Assert.IsTrue(instance.Equals(a, b));
            Assert.IsTrue(instance.Equals(b, a)); //test both ways round to ensure that equals is commutative (thanks https://english.stackexchange.com/a/471083/60075)
        }
        [TestMethod()]
        public void NonMatchingItemsDifferTest()
        {
            var instance = new ImmutableDictionaryEqualityComparer<string, string>();
            var a = (new Dictionary<string, string>() { { "One", "A" }, { "Two", "B" } }).ToImmutableDictionary();
            var b = (new Dictionary<string, string>() { { "One", "A" }, { "Two", "X" } }).ToImmutableDictionary();
            var c = (new Dictionary<string, string>() { { "One", "X" }, { "Two", "B" } }).ToImmutableDictionary();
            var d = (new Dictionary<string, string>() { { "One", "A" }, { "Two", "B" }, { "Three", "C" } }).ToImmutableDictionary();
            var e = (new Dictionary<string, string>()).ToImmutableDictionary();
            var f = (ImmutableDictionary<string, string>)null;
            Assert.IsFalse(instance.Equals(a, b));
            Assert.IsFalse(instance.Equals(b, a));
            Assert.IsFalse(instance.Equals(a, c));
            Assert.IsFalse(instance.Equals(c, a));
            Assert.IsFalse(instance.Equals(a, d));
            Assert.IsFalse(instance.Equals(d, a));
            Assert.IsFalse(instance.Equals(a, e));
            Assert.IsFalse(instance.Equals(e, a));
            Assert.IsFalse(instance.Equals(a, f));
            Assert.IsFalse(instance.Equals(f, a));
        }
        [TestMethod()]
        public void TwoNullsMakeARightTest()
        {
            var instance = new ImmutableDictionaryEqualityComparer<string, string>();
            var a = (ImmutableDictionary<string, string>)null;
            var b = (ImmutableDictionary<string, string>)null;
            Assert.IsTrue(instance.Equals(a, b));
            Assert.IsTrue(instance.Equals(b, a));
        }
        [TestMethod()]
        public void NullDoesNotMatchNonNullTest()
        {
            var instance = new ImmutableDictionaryEqualityComparer<string, string>();
            var a = (new Dictionary<string, string>() { { "One", "A" }, { "Two", "B" } }).ToImmutableDictionary();
            var b = (ImmutableDictionary<string, string>)null;
            Assert.IsFalse(instance.Equals(a, b));
            Assert.IsFalse(instance.Equals(b, a));
        }
    }
}