When Do You Need To Implement "GetHashCode?"

[Dad]

Hi,

A number of interfaces, e.g., IEqualityComparer, include GetHashCode.
When does it need to be implemented? I usually just return 0 or 1.

Thanks,
Gary

 

[Marc Gravell]

In short, any time you expect to use hash-logic on the item - for
example, use it as the key in a lookup.

GetHashCode() is used as a mechanism for doing a hash-match equality
test, in particular for building hash-tables, such as in
Dictionary<TKey, TValue> etc. In this case, the hash-code (or a
modulo) is used to split the items into different buckets; it is
further used to to hash-match equality tests.

The rules are that if the hash match of 2 items is different they
*can't* be the same; if it is the same, then check the actual equality
test (which mihgt be more expensive).

By returning a constant value, you are a: forcing everything into the
same bucket, and b: forcing the system to check every item for
equality, rather than being able to just look at those with matching
hash values. Ideally, the hash-code would be generated from something
immutable, or which you *expect* to be immutable while the item is
used as a key. Otherwise chaos breaks out, as it can fail to find the
item you know is there...

If none of that makes sense, post back...

Marc

 

[Jon Skeet [C# MVP]]

A number of interfaces, e.g., IEqualityComparer, include GetHashCode.
When does it need to be implemented?

Well, you should always implement it when you're providing an equality
definition, unless you're absolutely *sure* that the type will never be
used for any kind of hashing.

I usually just return 0 or 1.

That's going to make your type behave very badly when it's used as a
hashtable key.

 

[Marc Gravell]

With example; the first works and quickly; the second works, but
because it returns a constant hash the performance is terrible; the
third fails to find the key because the hash-code never matches
itself:


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;

struct Sane {
public readonly int Value;
public Sane(int value) { Value = value; }
public override int GetHashCode(){
return Value.GetHashCode();
}
public override bool Equals(object obj) {
return ((Sane)obj).Value == Value;
}
public static Sane Create(int value) {
return new Sane(value);
}
}
struct KeepMoving {
static int lastHash;
public readonly int Value;
public KeepMoving(int value) { Value = value; }
public override int GetHashCode() {
return Interlocked.Increment(ref lastHash);
}
public override bool Equals(object obj) {
return ((KeepMoving)obj).Value == Value;
}
public static KeepMoving Create(int value) {
return new KeepMoving(value);
}
}
struct NeverMove {
public readonly int Value;
public NeverMove(int value) { Value = value; }
public override int GetHashCode() {
return 0;
}
public override bool Equals(object obj) {
return ((NeverMove)obj).Value == Value;
}
public static NeverMove Create(int value) {
return new NeverMove(value);
}
}

static class Program
{
static void Main()
{
Test<Sane>(Sane.Create);
Test<NeverMove>(NeverMove.Create);
Test<KeepMoving>(KeepMoving.Create);
}

static void Test<TKey>(Func<int, TKey> ctor)
{
Stopwatch watch = new Stopwatch();
Dictionary<TKey, string> data = new Dictionary<TKey,
string>();
watch.Start();
TKey knownKey = ctor(-1);
data.Add(knownKey, "Foo");
for (int i = 0; i < 20000; i++)
{
data.Add(ctor(i), "Bar");
}
string foo = data[knownKey];
watch.Stop();
Console.WriteLine("{0}: {1}", typeof(TKey),
watch.ElapsedMilliseconds);
}

}