GetHashCode – Does it return unique values for different inputs?

The Object class of the .NET framework has got a virtual method, say, GetHashCode that other classes could override to provide a custom implementation. This function is suitable for use in hashing algorithms like a hash table. The return value [of the default implementation] is and has never been meant to be used as a unique key. Although, an ideal implementation would guarantee that, however, it is impossible or impractical.

If you are going to implement your own GetHashCode method, you need to keep the following three criterias in your mind:

• If two objects of the same type represent the same value, the hash function must return the same constant value for either object.
• For the best performance, a hash function must generate a random distribution for all input.
• The hash function must return exactly the same value regardless of any changes that are made to the object.

Many people believe (unfortunately) that the default implementation of String.GetHashCode function returns a unique number for different input values. However, Mashiharu’s sample states that the two following different string, produces the same hash code [on .NET FX 2.0]:

Trace.WriteLine("0:93121".GetHashCode());
Trace.WriteLine("0:2546870".GetHashCode());

Having this in mind, the GetHashCode function could be implemented by XORing the field values with each other:

public struct MyStruct1
{
    public int field1;
    public int field2;

    public override int GetHashCode()
    {
        return field1 ^ field2;
    }
}

Another common approach is to use a prime#:

public struct MyStruct2
{
    public int field1;
    public int field2;

    public override int GetHashCode()
    {
        return 19 * field1.GetHashCode() + 1 * field2.GetHashCode();
    }
}

where 19 is a prime#.

There are more complicated approaches each of which deserve a separate post. Whatever your approach is, just follow those above-mentioned rules. For more information, and some implementations of the GetHashCode, checkout the following sites:

1. Microsoft Developer Network (MSDN)
2. Frank Hileman’s notes on hash functions
3. Ian Griffiths, Paul Hsieh & Mashiharu.
4. Wikipedia