Guidelines and rules for GetHashCode

re: Guidelines and rules for GetHashCode

Martijn — Tue, 10 Jul 2012 15:55:47 GMT

Thank you very much for this post, which was pointed out to me on stackoverflow: stackoverflow.com/.../11411100

The collary of

"Rule: the integer returned by GetHashCode must never change while the object is contained in a data structure that depends on the hash code remaining stable" (thus, Equality comparison should never change while the object is contained in a datastructure that depends on equality - but other analogies also might be appropriate), I came up with the following rule (which is in fact more-or-less equal to the above rule.):

"GetHashCode should never depend on values that are mutable"

re: Guidelines and rules for GetHashCode

Marc Brooks — Fri, 06 May 2011 22:25:28 GMT

Oliver, yes, I reported that bug here: http://bit.ly/aSkUIm (and as usual, Microsoft decided to close as Won't Fix)

I've written extensively about hashing here: http://bit.ly/9qNcga

re: Guidelines and rules for GetHashCode

Pavel Minaev [MSFT] — Thu, 03 Mar 2011 23:24:08 GMT

Oh, and here's one more very good reason why you should always override Equals and GetHashCode on your structs in practice:

connect.microsoft.com/.../valuetype-equals-is-incorrect

re: Guidelines and rules for GetHashCode

Pavel Minaev [MSFT] — Thu, 03 Mar 2011 23:21:30 GMT

>> What makes you think a fully general implementation of this could be more efficient than it is?

Given that ValueType is one of the "magical" CLR types about which the runtime has special knowledge, it's quite possible - for example, the runtime could detect that your struct does not override Equals/GetHashCode, and generate its own (separately for every struct) that accesses fields directly.

>> Likewise for strings, "a" and "a" should be equal (even though the object ref may not be) - Tuple, String, Uri and XName, I see. I think then you could say that you ought to implement GetHashCode when you want the Equals() operator to be a logical Equals and not a ReferenceEquals? is that a fair characterization?

Pretty much, yes. Equals and GetHashCode always go hand in hand - if you're not overriding Equals, the default GetHashCode is good as it is. If I remember correctly, C# compiler will even warn if you override one but not the other.

Ultimately, the point is that for all those types like String, reference equality is mostly meaningless since you don't derive anything useful out of knowing whether it is the same object or not. Hence why you'd want to default to value comparisons. If anyone actually does care about object identity (e.g. for strings, this is sometimes used as an optimization, either with interning or with a local symbol table, like XmlNameTable in System.Xml), they can always use Object.ReferenceEqual.

Usually, for those kinds of types, operator== is also overloaded: out of those listed, for String this is done on language level, Uri and XName actually do overload it, and Tuple doesn't overload it because there is no clear way to propagate language-dependent equality semantics of tuple components (which can differ e.g. between C#/VB).

re: Guidelines and rules for GetHashCode

Alex Lo — Thu, 03 Mar 2011 21:26:33 GMT

@Random / Pavel

I think I understand your points better now. For structs, as they are value types you'd expect Equals() to work when two have the same content, therefore the GetHashCode should be the same between two with equal content. Likewise for strings, "a" and "a" should be equal (even though the object ref may not be) - Tuple, String, Uri and XName, I see. I think then you could say that you ought to implement GetHashCode when you want the Equals() operator to be a logical Equals and not a ReferenceEquals? is that a fair characterization?

re: Guidelines and rules for GetHashCode

Random832 — Thu, 03 Mar 2011 14:35:29 GMT

"so for structs it is a matter of the ValueType.GetHashCode() being inefficient - ok - why isnt this fixed in the CLR?"

What makes you think a fully general implementation of this could be more efficient than it is? The reason you're supposed to override it is to provide an implementation that's _not_ fully general and doing lots of extra checking that your type doesn't need [e.g. iterating over the fields with reflection to see if any of them override GetHashCode]

"But what is the advantage of what you propose for classes that 'is an "reference value type" (i.e. the interesting part about it is solely the data that it represents, not its object identity; this should generally also imply immutability).'? What does that add?"

Well, the most common example of a "reference value type" is String. How would you feel if you were unable to reliably use a String as a key in a hash table?

re: Guidelines and rules for GetHashCode

Alex Lo — Wed, 02 Mar 2011 19:17:45 GMT

@Pavel,

so for structs it is a matter of the ValueType.GetHashCode() being inefficient - ok - why isnt this fixed in the CLR?

But what is the advantage of what you propose for classes that 'is an "reference value type" (i.e. the interesting part about it is solely the data that it represents, not its object identity; this should generally also imply immutability).'? What does that add?

re: Guidelines and rules for GetHashCode

Paul G — Wed, 02 Mar 2011 14:01:37 GMT

Good article, thanks. A good part two would expand on some of the comments with strategies for creating hash values.

In the past I've been stuck in the situation of not fully understanding how the hash value was used internally (only that equal objects should return equal hashes). Therefore when implementing for objects with mixtures of strings and values I've often found myself concatenating the values into a string (eg name + "," + age) and then returning .GetHashCode() of the string.

It seems too easy. Is there a downside to this approach?

re: Guidelines and rules for GetHashCode

Bill P. Godfrey — Wed, 02 Mar 2011 09:18:52 GMT

Correction. I was thinking of the Thread ID, not the Process ID.

re: Guidelines and rules for GetHashCode

Simon Buchan — Wed, 02 Mar 2011 04:10:42 GMT

@BinaryCode: Wow, that was fast, thanks!