Equals is used. GetHashCode is not

Question

I have implemented the class below:

public class carComparer : IEqualityComparer<Car>
    {
        public bool Equals(Car car1, Car car2)
        {
                if (car1 == null || car2 == null)
                    return false;

                return (car1.description == car2.description);
        }

        public int GetHashCode(Car car)
        {
            unchecked 
            {
                int hash = 17;
                hash = hash * 29 + car.id.GetHashCode();
                hash = hash * 29 + car.description.GetHashCode();
                return hash;
            }
        }

    }

Now see this:

Car p1 = new Car() { id = Guid.NewGuid(), description = "Test1" };
        Car p2 = new Car() { id = Guid.NewGuid(), description = "Test1" };
        Car p3 = new Car() { id = Guid.NewGuid(), description = "Test1" };
        Car p4 = new Car() { id = Guid.NewGuid(), description = "Test1" };
        var hash = new HashSet<Car>();
        hash.Add(p1);
        hash.Add(p2);

        var hash2 = new HashSet<Car>();
        hash2.Add(p3);
        hash2.Add(p4);

        var carComparer = new CarComparer();
        Assert.That(hash, Is.EquivalentTo(hash2).Using(carComparer));

I put breakpoints in .equals and .hashcode. Equals is used; but GetHashCode is not. Why?

Answer 1

You are comparing two HashSet using NUnit Is.EquivalentTo. There is no reason for it to call GetHashCode - it basically compares two collections for equality of its members. That's why GetHashCode is never called and Equals is called to compare two items from different HashSets for equality. Your hashsets could as well be lists or any other enumerable - that doesn't change anything when comparing two collections.

You might expect GetHashCode to be called when you add item to HashSet - but it's not so, because at this point your carComparer is not yet known - you don't pass it to HashSet constructor. If you will do it like this:

var hash = new HashSet<Car>(new carComparer());

Then GetHashCode would be called when you add new item to corresponding HashSet.

Answer 2

GetHashCode is typically used in a hash-table-lookup.

The GetHashCode does not have to be guaranteed unique and therefor is not a valid IsEqual test.

For the GetHashCode to be used, use this constructor of the HashSet:

https://msdn.microsoft.com/en-us/library/bb359100(v=vs.110).aspx

So in order to use the GetHashCode method, you'll need to use:

var hash = new HashSet<Car>(carComparer);

Note that the hash will be verified when adding your object to the hashset.

The Comparer is then used in the HashSet.Add method, within this call:

private int InternalGetHashCode(T item)
{
  if ((object) item == null)
    return 0;

  //this._comparer is set during the constructor call
  return this._comparer.GetHashCode(item) & int.MaxValue;
}

For obvious reasons this makes the Comparer a read only property.

So, to sum up;

The GetHashCode is not used because, since it is typically used in a hash-table-lookup-creation, you'll need to provide it to the HashSet before you start adding items.

The IsEqual is used due to obvious reasons; and if it's not: see @dasblinkenlight's answer.

Answer 3

This happens because of the algorithm used in IsEquivalent to decide equivalency: the implementation constructs what they call a "collection tally" object from the collection that you expect, and then try removing items of the actual collection from it one-by-one:

public bool TryRemove(IEnumerable c) {
    foreach (object o in c)
        if (!TryRemove(o))
            return false;
    return true;
}

public bool TryRemove(object o) {
    for (int index = 0; index < list.Count; index++)
        if (ItemsEqual(list[index], o)) {
            list.RemoveAt(index);
            return true;
        }
    return false;
}

You can see that NUnit uses a relatively inefficient O(n²) algorithm instead of constructing a hash set for O(n) efficiency. This would matter for larger sets, but since a typical collection in a unit test has only a few items, there would be no noticeable difference.

ItemsEqual uses Equals from the equality comparer, but it has no need for hash code functionality (source code).