18

Possible Duplicate:
Why is it important to override GetHashCode when Equals method is overridden?

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

Community
  • 1
  • 1
jon37
  • 1,349
  • 3
  • 15
  • 29
  • Jared Parsons' blog has a good explanation of implementing equality and the reasons why GetHashCode is so important. [Properly Implementing Equality](http://blogs.msdn.com/jaredpar/archive/2008/04/28/properly-implementing-equality-in-vb.aspx) – Jim H. Mar 19 '09 at 00:09

4 Answers4

9

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).

JaredPar
  • 733,204
  • 149
  • 1,241
  • 1,454
1

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().

MarkusQ
  • 21,814
  • 3
  • 56
  • 68
  • Rather than thinking in terms of numbered buckets, I think it's simpler to say that hash codes are used to avoid comparisons. If the hashcode of object X is known--by whatever means--not to match the hashcode of object Y, there's no need to compare anything else about them. Buckets provide an easy way for code to ignore items whose hash codes can't possibly equal some particular value, but many collections explicitly compare hash codes even of items which get sorted into the same bucket. – supercat Jan 11 '17 at 22:22
0

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.

Greg Beech
  • 133,383
  • 43
  • 204
  • 250
0

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.

Daniel Earwicker
  • 114,894
  • 38
  • 205
  • 284