Why isn't .Except (LINQ) comparing things properly? (using IEquatable)

Question

I have two collections of my own reference-type objects that I wrote my own IEquatable.Equals method for, and I want to be able to use LINQ methods on them.

So,

List<CandyType> candy = dataSource.GetListOfCandy();
List<CandyType> lollyPops = dataSource.GetListOfLollyPops();
var candyOtherThanLollyPops = candy.Except( lollyPops );

According to the documentation of .Except, not passing an IEqualityComparer should result in EqualityComparer.Default being used to compare objects. And the documentation for the Default comparer is this:

"The Default property checks whether type T implements the System.IEquatable generic interface and if so returns an EqualityComparer that uses that implementation. Otherwise it returns an EqualityComparer that uses the overrides of Object.Equals and Object.GetHashCode provided by T."

So, because I implement IEquatable for my object, it should use that and work. But, it doesn't. It doesn't work until I override GetHashCode. In fact, if I set a break point, my IEquatable.Equals method never gets executed. This makes me think that it's going with plan B according to its documentation. I understand that overriding GetHashCode is a good idea, anyway, and I can get this working, but I am upset that it is behaving in a way that isn't in line with what its own documentation stated.

Why isn't it doing what it said it would? Thank you.

Answer 1

Hazarding a guess, are these different classes? I think by default IEquatable only works with the same class. So it might by falling back to the Object.Equal method.

Answer 2

The interface IEqualtyComparer<T> has these two methods:

bool Equals(T x, T y);
int GetHashCode(T obj);

A good implementation of this interface would thus implement both. The Linq extension method Except relies on the hash code in order to use a dictionary or set lookup internally to figure out which objects to skip, and thus requires that proper GetHashCode implementation.

Unfortunately, when you use EqualityComparer<T>.Default, that class does not provide a good GetHashCode implementation by itself, and relies on the object in question, the type T, to provide that part, when it detects that the object implements IEquatable<T>.

The problem here is that IEquatable<T> does not in fact declare GetHashCode so it's much easier to forget to implement that method properly, contrasted with the Equals method that it does declare.

So you have two choices:

• Provide a proper IEqualityComparer<T> implementation that implements both Equals and GetHashCode
• Make sure that in addition to implementing IEquatable<T> on your object, implement a proper GetHashCode as well

Answer 3

After investigation, it turns out things aren't quite as bad as I thought. Basically, when everything is implemented properly (GetHashCode, etc.) the documentation is correct, and the behavior is correct. But, if you try to do something like implement IEquatable all by itself, then your Equals method will never get called (this seems to be due to GetHashCode not being implemented properly). So, while the documentation is technically wrong, it's only wrong in a fringe situation that you'd never ever want to do (if this investigation has taught me anything, it's that IEquatable is part of a whole set of methods you should implement atomically (by convention, not by rule, unfortunately)). Good sources on this are:

http://stackoverflow.com/questions/1307493/is-there-a-complete-iequatable-implementation-reference

http://msdn.microsoft.com/en-us/library/ms131190.aspx

http://blogs.msdn.com/irenak/archive/2006/07/18/669586.aspx