7
\$\begingroup\$

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

    }
}
\$\endgroup\$
  • \$\begingroup\$ NB: After posting realised that my GetHashCode method doesn't handle nulls; so have since amended the first line to if (obj == null) return 0; long hashCode = obj.Count + 1;; so that null is handled, and an empty dictionary has a different hashcode to a null one. \$\endgroup\$ – JohnLBevan Oct 31 '18 at 10:52
  • \$\begingroup\$ You must not add the improved version to the question. Please post a self-answer instead... it'll be rolledback otherwise... \$\endgroup\$ – t3chb0t Nov 1 '18 at 10:40
7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks @PieterWitvoet ; that's a very good point. In my scenario, after entry the object used as the key would not be amended after insertion, but will rethink my approach since agree that this would be unexpected behaviour / may come back to bite someone in the future. \$\endgroup\$ – JohnLBevan Oct 31 '18 at 13:48
  • \$\begingroup\$ Related: found a good blog post with a more verbose explanation of this issue (i.e. why mutable reference types should not be used as keys): blog.markvincze.com/… \$\endgroup\$ – JohnLBevan Oct 31 '18 at 14:47
  • 1
    \$\begingroup\$ FYI: Issue resolved by simply replacing my IDictionary<TKey,TValue> with IImmutableDictionary<TKey,TValue> (more info here: stackoverflow.com/a/24033776/361842), which prevents the above scenario whilst keeping what's needed for my requirements. \$\endgroup\$ – JohnLBevan Oct 31 '18 at 15:01
0
\$\begingroup\$

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));
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I still can't say I like this whole approach. It's taking something efficient (dictionary lookups) and making it easy to use in an inefficient manner (repeatedly expensive hash-code generation and value comparison). Repeatedly, because despite the immutable nature of the key dictionaries, each GetHashCode call has to check all content again every time (oh, and what if that content is mutable?) I'm curious, what's the intended use-case for this? I guess it's only meant to be used with relatively small keys? \$\endgroup\$ – Pieter Witvoet Nov 1 '18 at 13:15
  • \$\begingroup\$ My plan is to use it as a poor man's cache (i.e. for objects which are expensive to create, but share the application's lifetime). At some point I'd likely switch my cache key from IImmutableDictionary to some kind of IConfigutionSetting, allowing me to create more targetted configuration settings classes; but initially I just wanted to run up something quick and dirty for my immediate use case. As you say, the number of items in each key would be small; and also the number of items in the dictionary which uses this key. \$\endgroup\$ – JohnLBevan Nov 1 '18 at 14:01
  • 1
    \$\begingroup\$ I could probably get away with a simpler hashing tactic based on the most likely settings's values' (i.e. the values most likely to differ between keys), but I'd wanted to make the solution general purpose. I guess another option to improve this would be to allow an argument to passed to the comparer's constructor allowing more targeted generation; i.e. so the hash code used could target one specific property if we expect only one setting's value to differ between each key, vs using the code above when we don't know where the differences are likely to occur. \$\endgroup\$ – JohnLBevan Nov 1 '18 at 14:05
  • \$\begingroup\$ I'm still wondering why the key has to be a dictionary. A simple custom ISet as a compound-key would do too. If you are able to replace this with IConfigutionSetting later then it's probably already overengineered. \$\endgroup\$ – t3chb0t Nov 2 '18 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.