.net - Using of IEqualityComparer<T> interface and EqualityComparer<T> class in C#

Question

I am programming a circular linked list using this article as help.

In a function that searches in this list for a node with a given value

    public Node<T> Find(T item)
    {
        Node<T> node = FindNode(head, item);
        return node;
    }

    Node<T> FindNode(Node<T> node, T valueToCompare)
    {
        Node<T> result = null;
        if (comparer.Equals(node.Value, valueToCompare))
            result = node;
        else if (result == null && node.Next != head)
            result = FindNode(node.Next, valueToCompare);
        return result;
    }

an author uses an IEqualityComparer<T> comparer object, which is initialized with a property EqualityComparer<T>.Default in one of constructors. Can you please explain me an idea of using of these interface (IEqualityComparer<T>) and class (EqualityComparer<T>) here? I had read MSDN, but I didn't understand the principles of working and using of them.

Answer 1

IEqualityComparer<in T> is an interface that will handle equality comparisons for your collection. Your collection will delegate equiality comparisons to this interface. You may ask, why don't just call the Equals method?

Because there can be several kinds of possible comparisons. Let's take an easy example: are "Abc" and "ABC" equal? It depends. "Abc".Equals("ABC") == false but what if you want case insensitivity?

This is why your collection should delegate the equality comparisons to a different class. By composing classes, you'll respect the single responsibility principle: Your collection knows how to store the items, and the equality comparer knows if they're equal.

An example with sets:

var caseSensitive = new HashSet<string>(StringComparer.Ordinal) // The default anyway
{
    "Abc", "ABC"
};

var caseInsensitive = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "Abc", "ABC"
};

The results will be:

caseSensitive.Count == 2
caseInsensitive.Count == 1

caseSensitive.Contains("aBc") == false
caseInsensitive.Contains("aBc") == true

Here you have two completely different set semantics using the same HashSet class.

Now, what's in an IEqualityComparer<in T>?

• bool Equals(T x, T y);: This method does just what you'd expect it to: it returns true if x should be considered equal to y. Just like the mathematical equality, it must be:
  • reflexive: Equals(x, x) == true
  • symmetric: Equals(x, y) == Equals(y, x)
  • transitive: if Equals(x, y) && Equals(y, z) then Equals(x, z)

• int GetHashCode(T obj); this one may be trickier to get right. For each obj, it should return a hash code wilth the following properties:
  • it should never change
  • if Equals(x, y) then GetHashCode(x) == GetHashCode(y)
  • there should be as few collisions as possible

Note that this does not imply that if GetHashCode(x) == GetHashCode(y) then Equals(x, y). Two objects can have the same hash code but be inequal (there can be at most 0xFFFFFFFF possible hash codes after all).

Collections often use the hash code to organize their items. For example, the HashSet will know that if two objects don't have the same hash code, they won't be equal and thus can organize its buckets accordingly. Hash codes are just an optimization.

Now, what's EqualityComparer<T>.Default? It's a conventient shortcut for an IEqualityComparer<T> that will use an object's own Equals and GetHashCode functions. This is a good default value as this is what you want to do most of the time: while strings can have multiple natural comparison types, this is not the case for integers for instance.

EqualityComparer<T>.Default will handle a couple special cases:

• if T is IEquatable<T>, it will use the IEquatable<T> interface
• if T is Nullable<U> and U is IEquatable<U> it will handle the case properly
• it will optimize for a couple special cases: byte[] and int-basd Enum.