C#: How would you unit test GetHashCode?

Question

Testing the Equals method is pretty much straight forward (as far as I know). But how on earth do you test the GetHashCode method?

Answer 1

From personal experience. Aside from obvious things like same objects giving you same hash codes, you need to create large enough array of unique objects and count unique hash codes among them. If unique hash codes make less than, say 50% of overall object count, then you are in trouble, as your hash function is not good.

        List<int> hashList = new List<int>(testObjectList.Count);
        for (int i = 0; i < testObjectList.Count; i++)
        {
            hashList.Add(testObjectList[i]);
        }

        hashList.Sort();
        int differentValues = 0;
        int curValue = hashList[0];
        for (int i = 1; i < hashList.Count; i++)
        {
            if (hashList[i] != curValue)
            {
                differentValues++;
                curValue = hashList[i];
            }
        }

        Assert.Greater(differentValues, hashList.Count/2);

Answer 2

In addition to checking that object equality implies equality of hashcodes, and the distribution of hashes is fairly flat as suggested by Yann Trevin (if performance is a concern), you may also wish to consider what happens if you change a property of the object.

Suppose your object changes while it's in a dictionary/hashset. Do you want the Contains(object) to still be true? If so then your GetHashCode had better not depend on the mutable property that was changed.

Answer 3

You create separate instances with the same value and check that the GetHashCode for the instances returns the same value, and that repeated calls on the same instance returns the same value.

That is the only requirement for a hash code to work. To work well the hash codes should of course have a good distribution, but testing for that requires a lot of testing...

Answer 4

Test that two distinct objects which are equal have the same hash code (for various values). Check that non-equal objects give different hash codes, varying one aspect/property at a time. While the hash codes don't have to be different, you'd be really unlucky to pick different values for properties which happen to give the same hash code unless you've got a bug.

Answer 5

Gallio/MbUnit v3.2 comes with convenient contract verifiers which are able to test your implementation of GetHashCode() and IEquatable<T>. More specifically you may be interested by the EqualityContract and the HashCodeAcceptanceContract. See here, here and there for more details.

public class Spot
{
  private readonly int x;
  private readonly int y;

  public Spot(int x, int y)
  {
    this.x = x;
    this.y = y;
  }

  public override int GetHashCode()
  {
    int h = -2128831035;
    h = (h * 16777619) ^ x;
    h = (h * 16777619) ^ y;
    return h;
  }
}

Then you declare your contract verifier like this:

[TestFixture]
public class SpotTest
{
  [VerifyContract]
  public readonly IContract HashCodeAcceptanceTests = new HashCodeAcceptanceContract<Spot>()
  {
    CollisionProbabilityLimit = CollisionProbability.VeryLow,
    UniformDistributionQuality = UniformDistributionQuality.Excellent,
    DistinctInstances = DataGenerators.Join(Enumerable.Range(0, 1000), Enumerable.Range(0, 1000)).Select(o => new Spot(o.First, o.Second))
  };
}

Answer 6

It would be fairly similar to Equals(). You'd want to make sure two objects which were the "same" at least had the same hash code. That means if .Equals() returns true, the hash codes should be identical as well. As far as what the proper hashcode values are, that depends on how you're hashing.