Why we implement GetHashCode in IEqualityComparer?

Question

I want to get distinct items from List in C# by using IEqualityComparer interface. But I don't know about GetHashCode. I have implement both GetHashCode and Equals methods. And how can I call Equals method to get distinct items from a list having user define data type.

I added a pretty full on answer to this here: http://stackoverflow.com/questions/4095395/whats-the-role-of-gethashcode-in-the-iequalitycomparert-in-net/4096774#4096774 — sheikhjabootie, Oct 09 '11 at 02:22
possible duplicate of [whats-the-role-of-gethashcode-in-the-iequalitycomparert-in-net](http://stackoverflow.com/questions/4095395/whats-the-role-of-gethashcode-in-the-iequalitycomparert-in-net?lq=1) — nawfal, Jun 02 '13 at 15:30

score 5 · Answer 1 · answered Sep 30 '11 at 10:13

5

You can use the Distinct extension method passing it your custom equality comparer.

The reason why you need GetHashCode() is that without it you need O(n^2) comparisons. With GetHashCode() the items can be divided into buckets, which leads to O(n) for a good hash implementation.

If the item type is your own, you can override Equals and GetHashCode in the type itself instead of creating an IEqualityComparer<T>

answered Sep 30 '11 at 10:13

CodesInChaos

106,488
23
218
262

@JonHanna 1+2+3+...+n-1 = 0.5*n*(n-1) => O(n^2) Not sure how you got O(n!). There are that many edges is a graph with n nodes. You can also easily see that the naive implementation of `Distinct` has two nested loops and no recursion. – CodesInChaos Dec 19 '11 at 12:51
Yes. On consideration, you are completely correct. Indeed, on consideration, I can't even think what on earth made me think it would be O(n!). – Jon Hanna Dec 19 '11 at 13:33

score 4 · Accepted Answer · answered Sep 30 '11 at 10:12

And how can I call Equals method to get distinct items from a list having user define data type.

Use the overload of Enumerable.Distinct that takes an IEqualityComparer to get the distinct items from a sequence using your custom equality comparer.

Why we implement GetHashCode in IEqualityComparer?

So that the IEqualityComparer can be used as a test for equality in a hash table (hash the items as per the IEqualityComparer.GetHashCode method, use IEqualityComparer.Equals to check for equality when needed (searching for an item in the hash table, for example).

score 0 · Answer 3 · edited May 23 '17 at 11:44

Why we implement GetHashCode in IEqualityComparer?

Because it gets called on IEqualityComparer, usually first, before Equals, at least for the LINQ extension methods which require IEqualityComparer. Otherwise it would be questionable whether you'd really need to implement GetHashCode for determining equality, since you could just use the Equals method for that. Why does LINQ prefer to call GetHashCode? See Why use GetHashCode() over Equals()?

Why we implement GetHashCode in IEqualityComparer?

3 Answers3