What can go wrong if one fails to override GetHashCode() when overriding Equals()?

Question

In C#, what specifically can go wrong if one fails to override GetHashCode() when overriding Equals()?

Answer 1

The most visible way is for mapping structures.

Any class which does this will have unpredictable behavior when used as the Key for a Dictionary or HashTable. The reason being is that the implementation uses both GetHashCode and Equals to properly find a value in the table. The short version of the algorithm is the following

1. Take the modulus of the HashCode by the number of buckets and that's the bucket index
2. Call .Equals() for the specified Key and every Key in the particular bucket.
3. If there is a match that is the value, no match = no value.

Failing to keep GetHashCode and Equals in sync will completely break this algorithm (and numerous others).

Answer 2

Jared Parsons' blog has a good explanation of implementing equality and the reasons why GetHashCode is so important.

Properly Implementing Equality

Answer 3

If you do not override GetHashCode, anything that compares your objects may get it wrong.

As it is documented that GetHashCode must return the same value if two instances are equal, then it is the prerogative of any code which wishes to test them for equality to use GetHashCode as a first pass to group objects which may be equal (as it knows that objects with different hash codes cannot be equal). If your GetHashCode method returns different values for equal objects then they may get into different groups in the first pass and never be compared using their Equals method.

This could affect any collection-type data structure, but would be particularly problematic in hash-code based ones such as dictionaries and hash-sets.

In short: Always override GetHashCode when you override Equals, and ensure their implementations are consistent.

Answer 4

Any algorithm that uses the Key will fail to work, assuming it relies on the intended behaviour of hash keys.

Two objects that are Equal should have the same hash key value, which is not remotely guaranteed by the default implementation.

Answer 5

Think of a hash / dictionary structure as a collection of numbered buckets. If you always put things in the bucket corresponding to their GetHashCode(), then you only have to search one bucket (using Equals()) to see if something is there. This works, provided you're looking in the right bucket.

So the rule is: if Equals() says two objects are Equal(), they must have the same GetHashCode().