Equals() contract for .NET Dictionary / IDictionary vs equals() contract for Java Map

Question

Nostalgic for Collections.unmodifiableMap(), I've been implementing a read-only IDictionary wrapper based on this discussion, and my unit test quickly ran into a problem:

Assert.AreEqual (backingDictionary, readOnlyDictionary);

fails, even though the key-value pairs match. I played around a little more, and it looks like at least (thank Simonyi)

Assert.AreEquals (backingDictionary, new Dictionary<..> { /* same contents */ });

does pass.

I took a quick look through the Dictionary and IDictionary documentation, and to my surprise I couldn't find any equivalent of the Java Map contract that two Maps with equal entrySet()s must be equal. (The docs say that Dictionary -- not IDictionary -- overrides Equals(), but don't say what that override does.)

So it looks like key-value equality in C# is a property of the Dictionary concrete class, not of the IDictionary interface. Is this right? Is it generally true of the whole System.Collections framework?

If so, I'd be interested to read some discussion of why MS chose that approach -- and also of what the preferred way would be to check for equality of collection contents in C#.

And finally, I wouldn't mind a pointer to a well-tested ReadOnlyDictionary implementation. :)

---

ETA: To be clear, I'm not looking for suggestions on how to test my implementation -- that's relatively trivial. I'm looking for guidance on what contract those tests should enforce. And why.

---

ETA: Folks, I know IDictionary is an interface, and I know interfaces can't implement methods. It's the same in Java. Nevertheless, the Java Map interface documents an expectation of certain behavior from the equals() method. Surely there must be .NET interfaces that do things like this, even if the collection interfaces aren't among them.

Answer 1

Overriding equals is normally only done with classes which have a degree of value semantics (e.g. string). Reference equality is what people are more often concerned about with most reference types and a good default, especially in cases which can be less than clear (are two dictionaries with exactly the same key-value-pairs but different equality-comparers [and hence adding the same extra key-value-pair could make them now different] equal or not?) or where value-equality is not going to be frequently looked for.

After all, you are looking for a case where two different types are considered equal. An equality override would probably still fail you.

All the more so as you can always create your own equality comparer quickly enough:

public class SimpleDictEqualityComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
{
    // We can do a better job if we use a more precise type than IDictionary and use
    // the comparer of the dictionary too.
    public bool Equals(IDictionary<TKey, TValue> x, IDictionary<TKey, TValue> y)
    {
        if(ReferenceEquals(x, y))
            return true;
        if(ReferenceEquals(x, null) || ReferenceEquals(y, null))
            return false;
        if(x.Count != y.Count)
            return false;
        TValue testVal = default(TValue);
        foreach(TKey key in x.Keys)
            if(!y.TryGetValue(key, out testVal) || !Equals(testVal, x[key]))
                return false;
        return true;
    }
    public int GetHashCode(IDictionary<TKey, TValue> dict)
    {
        unchecked
        {
            int hash = 0x15051505;
            foreach(TKey key in dict.Keys)
            {
                var value = dict[key];
                var valueHash = value == null ? 0 : value.GetHashCode();
                hash ^= ((key.GetHashCode() << 16 | key.GetHashCode() >> 16) ^ valueHash);
            }
            return hash;
        }
    }
}

That wouldn't serve all possible cases where one wants to compare dictionaries, but then, that was my point.

Filling up the BCL with "probably what they mean" equality methods would be a nuisance, not a help.

Answer 2

I would suggest using CollectionAssert.AreEquivalent() from NUnit. Assert.AreEqual() is really not meant for collections. http://www.nunit.org/index.php?p=collectionAssert&r=2.4

Answer 3

For later readers, here's what I've been told / been able to figure out:

1. The contract for .NET collections, unlike Java collections, doesn't include any specific behavior for Equals() or GetHashCode().
2. LINQ Enumerable.SequenceEqual() extension method will work for ordered collections, including dictionaries -- which present as IEnumerable<KeyValuePair>; KeyValuePair is a struct, and its Equals method uses reflection to compare the contents.
3. Enumerable provides other extension methods that can be used to cobble together a content equality check, such as Union() and Intersect().

I'm coming around to the idea that, convenient as the Java methods are, they might not be the best idea if we're talking about mutable collections, and about the typical implicit equals() semantics -- that two equal objects are interchangeable. .NET doesn't provide very good support for immutable collections, but the open-source PowerCollections library does.

Answer 4

public sealed class DictionaryComparer<TKey, TValue>
    : EqualityComparer<IDictionary<TKey, TValue>>
{
    public override bool Equals(
        IDictionary<TKey, TValue> x, IDictionary<TKey, TValue> y)
    {
        if (object.ReferenceEquals(x, y)) return true;
        if ((x == null) || (y == null)) return false;
        if (x.Count != y.Count) return false;

        foreach (KeyValuePair<TKey, TValue> kvp in x)
        {
            TValue yValue;
            if (!y.TryGetValue(kvp.Key, out yValue)) return false;
            if (!kvp.Value.Equals(yValue)) return false;
        }
        return true;
    }

    public override int GetHashCode(IDictionary<TKey, TValue> obj)
    {
        unchecked
        {
            int hash = 1299763;
            foreach (KeyValuePair<TKey, TValue> kvp in obj)
            {
                int keyHash = kvp.Key.GetHashCode();
                if (keyHash == 0) keyHash = 937;

                int valueHash = kvp.Value.GetHashCode();
                if (valueHash == 0) valueHash = 318907;

                hash += (keyHash * valueHash);
            }
            return hash;
        }
    }
}