Why IEqualityComparer has GetHashCode() method?

Question

IEqualityComparer in the namespace System.Collections.Generic has following methods:

bool Equals(T x, T y);
int GetHashCode(T obj);

Since this inteface is used to check equality of objects, the first method Equals makes sense. But why do we need to implement GetHashCode also? Why does it exist in the interface in the first place? When is it needed and why?

I'm using it with Enumerable.Distinct() method in the namespace System.Linq, and I'm surprised to see that even GetHashCode() is getting called, along with Equals(). Why? How does Distinct work?

score 8 · Accepted Answer · edited Feb 04 '16 at 13:55

8

For details on how Distinct works (or at least a simple example implementation) see my Edulinq blog post on it (~~old - 404~~).

To put it simply, a hash code which corresponds to the appropriate equality comparison makes it cheaper to create a set of items. That's useful in a lot of situations - such as Distinct, Except, Intersect, Union, Join, GroupJoin, GroupBy, ToLookup and so on.

edited Feb 04 '16 at 13:55

tomsseisums

13,168
19
83
145

answered Feb 24 '11 at 12:37

Jon Skeet

1,421,763
867
9,128
9,194

score 1 · Answer 2 · answered Feb 24 '11 at 12:35

1

GetHashCode is used in HashTables, Dictionaries and others to optimize the search. Have a look here: http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

answered Feb 24 '11 at 12:35

Daniel Hilgarth

171,043
40
335
443

1

I didn't answer that part. Is that really a reason to downvote my post? It's not wrong, because I only answered part of the question. – Daniel Hilgarth Feb 24 '11 at 12:39
@Daniel: I didn't downvote it. :|... +1 from me for partially answering my question. :) – Nawaz Feb 24 '11 at 12:43
@Nawaz: Think about how you'd implement Distinct... think about how similar a set is to the keys in a dictionary... – Jon Skeet Feb 24 '11 at 12:43
@Nawaz: I am sorry. Someone did and I interpreted your comment as the explanation, why you did it. – Daniel Hilgarth Feb 24 '11 at 12:44
@Jon Skeet : I'm reading your blog. It looks good. Have you explained such thing in your book? Actually, I want to learn such thing in detail. Kindly suggest me where should I start from. – Nawaz Feb 24 '11 at 12:45
@Nawaz: I don't go into that aspect in particular detail in the book. You may want to read through the whole of Edulinq though - the last post in the series has a table of contents. http://msmvps.com/blogs/jon_skeet/archive/2011/02/23/reimplementing-linq-to-objects-part-45-conclusion-and-list-of-posts.aspx – Jon Skeet Feb 24 '11 at 13:43
@Jon Skeet: Thanks. I also ordered your book, this edition : http://www.flipkart.com/depth-2nd-ed-jon-skeet-book-9350040607 – Nawaz Feb 24 '11 at 15:07
@Nawaz: Cool - hope you enjoy it :) – Jon Skeet Feb 24 '11 at 15:52
For those looking, Skeet's Edulinq series & Table of Contents is available here: http://codeblog.jonskeet.uk/2011/02/23/reimplementing-linq-to-objects-part-45-conclusion-and-list-of-posts/ – tomsseisums Feb 04 '16 at 13:56

score 0 · Answer 3 · answered Feb 24 '11 at 12:38

Because the Guidelines for Overriding Equals() and Operator == (C# Programming Guide) says:

It is recommended that any class that overrides Equals also override Object.GetHashCode.

This is because Hashtables etc expects that two objects that are equal have the same hashcode.

supercat · Answer 4 · 2012-12-03T22:27:57.670

The purpose of IEqualityComparer(Of T) is to allow the use of a comparison method which is semantically different from the default Object.Equals--one which may cause two objects to be considered equal even if Object.Equals would consider them different. Because equal objects must have equal hash codes, and because things which the EqualityComparer's Equals method considers equal but Object.Equals considers unequal might have different hash codes, it is necessary for the the EqualityComparer to use a different hash-coding method.

A more interesting situation exists with IEquatable(Of T). That is expected never to report two objects as equal if Object.Equals reports them unequal. For any unsealed class to implement IEquatable(Of T) is dangerous; too bad there's no generic constraint which would forbid the use of unsealed classes.

Why IEqualityComparer has GetHashCode() method?

4 Answers4