Why Is Valuetype.Gethashcode() Implemented Like It Is

Why is ValueType.GetHashCode() implemented like it is?

UPDATE: This answer was (in part) the basis of a blog article I wrote which goes into more details about the design characteristics of GetHashcode. Thanks for the interesting question!

---

I didn't implement it and I haven't talked to the people who did. But I can point out a few things.

(Before I go on, note that here I am specifically talking about hash codes for the purposes of balancing hash tables where the contents of the table are chosen by non-hostile users. The problems of hash codes for digital signing, redundancy checking, or ensuring good performance of a hash table when some of the users are mounting denial-of-service attacks against the table provider are beyond the scope of this discussion.)

First, as Jon correctly notes, the given algorithm does implement the required contract of GetHashCode. It might be sub-optimal for your purposes, but it is legal. All that is required is that things that compare equal have equal hash codes.

So what are the "nice to haves" in addition to that contract? A good hash code implementation should be:

1) Fast. Very fast! Remember, the whole point of the hash code in the first place is to rapidly find a relatively empty slot in a hash table. If the O(1) computation of the hash code is in practice slower than the O(n) time taken to do the lookup naively then the hash code solution is a net loss.

2) Well distributed across the space of 32 bit integers for the given distribution of inputs. The worse the distribution across the ints, the more like a naive linear lookup the hash table is going to be.

So, how would you make a hash algorithm for arbitrary value types given those two conflicting goals? Any time you spend on a complex hash algorithm that guarantees good distribution is time poorly spent.

A common suggestion is "hash all of the fields and then XOR together the resulting hash codes". But that is begging the question; XORing two 32 bit ints only gives good distribution when the inputs themselves are extremely well-distributed and not related to each other, and that is an unlikely scenario:

// (Updated example based on good comment!)
struct Control
{
    string name;
    int x;
    int y;
}

What is the likelihood that x and y are well-distributed over the entire range of 32 bit integers? Very low. Odds are much better that they are both small and close to each other, in which case xoring their hash codes together makes things worse, not better. xoring together integers that are close to each other zeros out most of the bits.

Furthermore, this is O(n) in the number of fields! A value type with a lot of small fields would take a comparatively long time to compute the hash code.

Basically the situation we're in here is that the user didn't provide a hash code implementation themselves; either they don't care, or they don't expect this type to ever be used as a key in a hash table. Given that you have no semantic information whatsoever about the type, what's the best thing to do? The best thing to do is whatever is fast and gives good results most of the time.

Most of the time, two struct instances that differ will differ in most of their fields, not just one of their fields, so just picking one of them and hoping that it's the one that differs seems reasonable.

Most of the time, two struct instances that differ will have some redundancy in their fields, so combining the hash values of many fields together is likely to decrease, not increase, the entropy in the hash value, even as it consumes the time that the hash algorithm is designed to save.

Compare this with the design of anonymous types in C#. With anonymous types we do know that it is highly likely that the type is being used as a key to a table. We do know that it is highly likely that there will be redundancy across instances of anonymous types (because they are results of a cartesian product or other join). And therefore we do combine the hash codes of all of the fields into one hash code. If that gives you bad performance due to the excess number of hash codes being computed, you are free to use a custom nominal type rather than the anonymous type.

Why should I *not* override GetHashCode()?

C# has built-in value types which provide value equality, whereas Java does not. So writing your own hashcode in Java may be a necessity, whereas doing it in C# may be a premature optimisation.

It's common to write a type to use as a composite key to use in a Dictionary/HashMap. Often on such types you need value equality (equivalence) as opposed to reference equality(identity), for example:

IDictionary<Person, IList<Movie> > moviesByActor; // e.g. initialised from DB
// elsewhere...
Person p = new Person("Chuck", "Norris");
IList<Movie> chuckNorrisMovies = moviesByActor[p];

Here, if I need to create a new instance of Person to do the lookup, I need Person to implement value equality otherwise it won't match existing entries in the Dictionary as they have a different identity.

To get value equality, you need an overridden Equals() and GetHashCode(), in both languages.

C#'s structs (value types) implement value equality for you (albeit a potentially inefficient one), and provide a consistent implementation of GetHashCode. This may suffice for many people's needs and they won't go further to implement their own improved version unless performance problems dictate otherwise.

Java has no such built-in language feature. If you want to create a type with value equality semantics to use as a composite key, you must implement equals() and correspondingly hashCode() yourself. (There are third-party helpers and libraries to help you do this, but nothing built into the language itself).

I've described C# value types as 'potentially inefficient' for use in a Dictionary because:

• The implementation of ValueType.Equals itself can sometimes be slow. This is used in Dictionary lookups.
• The implementation of ValueType.GetHashCode, whilst correct, can yield many collisions leading to very poor Dictionary performance also. Have a look at this answer to a Q by Jon Skeet, which demonstrates that KeyValuePair<ushort, uint> appears to always yield the same hashCode!

How is base.GetHashCode() implemented for a struct?

The coreclr repo has this comment:

Action: Our algorithm for returning the hashcode is a little bit complex. We look
for the first non-static field and get it's hashcode. If the type has no
non-static fields, we return the hashcode of the type. We can't take the
hashcode of a static member because if that member is of the same type as
the original type, we'll end up in an infinite loop.

However, the code isn't there, and it looks like that's not quite what happens. Sample:

using System;

struct Foo
{
    public string x;
    public string y;
}

class Test
{
    static void Main()
    {
        Foo foo = new Foo();
        foo.x = "x";
        foo.y = "y";
        Console.WriteLine(foo.GetHashCode());
        Console.WriteLine("x".GetHashCode());
        Console.WriteLine("y".GetHashCode());
    }
}

Output on my box:

42119818
372029398
372029397

Changing the value of y doesn't appear to change the hash code of foo.

However, if we make the fields int values instead, then more than the first field affects the output.

In short: this is complex, and you probably shouldn't depend on it remaining the same across multiple versions of the runtime. Unless you're really, really confident that you don't need to use your custom struct as a key in a hash-based dictionary/set, I'd strongly recommend overriding GetHashCode and Equals (and implementing IEquatable<T> to avoid boxing).

Is Object.GetHashCode() unique to a reference or a value?

Rules 1 & 3 are contradictory to me.

To a certain extent, they are. The reason is simple: if an object is stored in a hash table and, by changing its value, you change its hash then the hash table has lost the value and you can't find it again by querying the hash table. It is important that while objects are stored in a hash table, they retain their hash value.

To realize this it is often simplest to make hashable objects immutable, thus evading the whole problem. It is however sufficient to make only those fields immutable that determine the hash value.

Consider the following example:

struct Person {
    public readonly string FirstName;
    public readonly string Name;
    public readonly DateTime Birthday;

    public int ShoeSize;
}

People rarely change their birthday and most people never change their name (except when marrying). However, their shoe size may grow arbitrarily, or even shrink. It is therefore reasonable to identify people using their birthday and name but not their shoe size. The hash value should reflect this:

public int GetHashCode() {
    return FirstName.GetHashCode() ^ Name.GetHashCode() ^ Birthday.GetHashCode();
}

What is difference between GetHashCode implemented in Object and ValueType class?

Yes; value-types (structs) by default make their hash-code as a composite of the values of their fields. You can observe this by trying:

var s = new Point(1,2); // struct
Console.WriteLine(s.GetHashCode());
s.X = 22; // <=============== struct fields should usually be readonly!
Console.WriteLine(s.GetHashCode()); // different

Note that Equals obeys similar rules.

By contrast, a reference-type (class) uses, by default, the reference itself for both GetHashCode() and Equals(). The s.X = 22 will not impact a class:

var s = new Point(1,2); // class
Console.WriteLine(s.GetHashCode());
s.X = 22;
Console.WriteLine(s.GetHashCode()); // same

How can I identify a bad implementation of GetHashCode?

GetHashCode should match concept of "equal" for your classes/environment (in addition to be constant while in a container and fast).

In normal cases "equal" is comparing all fields of corresponding objects (value type comparison). In this case simple implementation that somehow merges hash codes of all fields will suffice.

My understanding that in NHibernate's case "equal" is significantly more tricky and as result you see complicated implementation.I believe it is mainly due to the fact that some object properties may not be yet available - in such case comparing "identity" of object is enough.

---

Related Topics