4

In .NET, Whenever we override Equals() method for a class, it is a normal practice to override the GetHashCode() method as well. Doing so will ensure better performance when the object is used in Hashtables and Dictionaries. Two keys are considered to be equal in Hashtable only if their GetHashCode() values are same. My question is why can't the Hashtables use Equals() method to compare the keys?, that would have removed the burden of overriding GetHashCode() method.

DivideByzero
  • 474
  • 4
  • 15
  • 3
    Possible duplicate of [Why is it important to override GetHashCode when Equals method is overridden?](http://stackoverflow.com/questions/371328/why-is-it-important-to-override-gethashcode-when-equals-method-is-overridden) – MethodMan Jan 12 '16 at 19:03
  • 3
    Have you looked at how hash tables work in general? If a dictionary has (say) 10000 keys, how would you expect a *quick* lookup without using hash codes? – Jon Skeet Jan 12 '16 at 19:05
  • @MethodMan I was not looking for a reason on why to override GetHashCode when Equals method is overriden. I was wondering why can't the Hashtables/Dictionaries use Equals() to determine if the keys are equal are not. Anyways, my question was answered by Habib and JonSkeet. Thanks ! – DivideByzero Jan 12 '16 at 19:18

3 Answers3

6

HastTable/Dictionaries use Equals in case of collision (when two hash codes are same).

Why don't they use only Equals ?

Because that would require a lot more processing than accessing/(comparing) integer value value (hash code). (Since hash codes are used as index so they have the complexity of O(1))

Habib
  • 219,104
  • 29
  • 407
  • 436
  • .NET dictionaries also use `GetHashCode` to determine which internal bucket an object falls into, further reducing the number of objects to compare. – Matthew Jan 12 '16 at 19:06
4

A HashSet (or HashTable, or Dictionary) uses an array of buckets to distribute the items, those buckets are indexed by the object's hash code (which should be immutable), so the search of the bucket the item is in is O(1).

Then it uses Equals within that bucket to find the exact match if there's more than one item with the same hashcode: that's O(N) since it needs to iterate over all items within that bucket to find the match.

If a hashset used only Equals, finding an item would be O(N) and you could aswell be using a list, or an array.

That's also why two equal items must have the same hashcode, but two items with the same hashcode don't necessarily need to be equal.

Jcl
  • 27,696
  • 5
  • 61
  • 92
1

Thus, for a given object instance, GetHashCode needs to reflect the logic of Equals, to some extent.

Now if you're overriding the Equals method, you're providing custom comparison logic. As an example, let's say your custom comparison logic involves only one particular data member of the instance. For a non-virtual GetHashCode method to be useful, it would have to be general enough to understand your custom Equals logic and be able to come up with a custom hash code function (one that only involves your chosen data member) on the spot.

It's not that easy to write such a sophisticated GetHashCode and it's not worth the trouble either, when the user can simply provide a custom one-liner that honors the initial requirement.

Community
  • 1
  • 1
Theodoros Chatzigiannakis
  • 28,773
  • 8
  • 68
  • 104