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

Answer 5

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

I think it is quite simple - IDictionary is an interface and interfaces can't have any implementations and in .NET world equality of two objects is defined through Equals method. So it is just impossible to override Equals for the IDictionary interface to allow it possesing "key-value equality".

Answer 6

you made a big mistake in your original post. You talked about the Equals() method in the IDictionary interface. That's the point!

Equals() is a virtual method of System.Object that classes can override. Interfaces don't implement methods at all. Instead, instances of interfaces are reference types, thus inheriting from System.Object and potentially declaring an override of Equals().

Now the point... System.Collections.Generic.Dictionary<K,V> does not override Equals. You said you implemented your IDictionary your own way, and reasonably overriden Equals, but look at your own code

Assert.AreEqual (backingDictionary, readOnlyDictionary); 

This method is basically implemented as return backingDictionary.Equals(readOnlyDictionary) and again here is the point.

Basic Equals() method returns false if two objects are instances of different classes, you cannot control that. Otherwise, if the two objects are of the same type, each member is compared via reflection (just members, not properties) using the Equals() approach instead of == (which is what the manual calls "value compare" instead of "reference compare")

So for first, I would not be surprised if Assert.AreEqual (readOnlyDictionary,backingDictionary); succeeds, because it would trigger a user-defined Equals method.

I have no doubts that approaches by other users in this thread work, but I just wanted to explain you what was the mistake in your original approach. Surely Microsoft would have better implemented an Equals method that compares the current instance to any other IDictionary instance, but, again, that would have gone outside the scope of the Dictionary class, which is a public stand-alone class and is not meant to be the only public available implementation of IDictionary. For example, when you define an interface, a factory and a protected class that implements it in a library, you might want to compare the class against other instances of the base interface rather than of the class itself which is not public.

I hope to have been of help to you. Cheers.