Implementing GetHashCode correctly

Question

I'd like to hear from the community on how I should go about implementing GetHashCode (or override it) for my object. I understand I need to do so if I override the equals method. I have implemented it a fair amount of times, sometimes just calling the base method. I understand that my object should equal another instance of the object if it contains the same details (members). What is the best way to get a hash code from the class's members?

Consider closing as duplicate of http://stackoverflow.com/a/720282/93922 — Tetsujin no Oni, Jan 25 '12 at 20:31
Before you do this, I recommend that you read and understand my article on it: http://blogs.msdn.com/b/ericlippert/archive/2011/02/28/guidelines-and-rules-for-gethashcode.aspx — Eric Lippert, Jan 25 '12 at 20:36
Thanks, I understand that this may be a common question and I should have done a little more hunting around. Thanks for your help — Zivka, Jan 25 '12 at 20:39
If you're not going to use the class as the key for a hash table, you don't actually need to override GetHashCode — phoog, Jan 26 '12 at 03:57
@EricLippert Your linked article seems unavailable by today (2021). Do you have an up-to-date version? — Fildor, Jan 28 '21 at 16:45
@Fildor: It is here: https://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/ — Eric Lippert, Jan 28 '21 at 19:51

score 64 · Accepted Answer · answered Jan 25 '12 at 20:31

64

Let's say your class looks like this:

class Frob {
    public string Foo { get; set; }
    public int Bar { get; set; }
    public double FooBar { get; set; }
}

Let's say you define equals so that two instances of Frob are equal if their Foo and their Bar are equal, but FooBar doesn't matter.

Then you should define GetHashCode in terms of Foo and Bar. One way is like this:

return this.Foo.GetHashCode() * 17 + this.Bar.GetHashCode();

Basically, you just want to incorporate all the fields that go into defining the equality. One way is to just keep accumulating and multiplying by 17 like I've done. It's fast, it's simple, it's correct, and it usually gives a good distribution.

answered Jan 25 '12 at 20:31

jason

236,483
35
423
525

8

I have a feeling this should be a question itself, but why 23? – George Duckett Jan 25 '12 at 20:32
1

Prime factor to make {2,1} and {1,2} differ. – Tetsujin no Oni Jan 25 '12 at 20:33
7

maybe point out that GetHashCode only tells you if two objects **might** be considered equal. There's still the posibility of a hash collision. – geofftnz Jan 25 '12 at 20:34
1

@geofftnz Or, even more specifically, GetHashCode is used to determine which bucket to put an object into when storing it in a hash. If your GetHashCode is poorly differentiating, it will create a long list which will be searched linearly when returning items from the HashTable, and will be a very bad key (read: collision-error-causing) for a Dictionary. – Tetsujin no Oni Jan 25 '12 at 20:37
http://stackoverflow.com/a/720282/93922 expands on this a bit. – Tetsujin no Oni Jan 25 '12 at 20:37
@TetsujinnoOni taking it even further, in some cases it should be difficult to reverse the hash, to make it harder for attackers to turn your hash table into a linked list (complexity-wise) and killing your CPU. Thus why we were running around patching servers in early Jan 2012. – geofftnz Jan 25 '12 at 22:30
90

Be careful with implementing `GetHashCode()` (and `Equals()`) as depending on mutable data, like here. If you put such object into a hash-based dictionary, and then mutate it, the dictionary won't work correctly anymore. Ideally, `GetHashCode()` (and `Equals()`) should depend only on immutable data. – svick Jan 25 '12 at 23:49
One of the expectations of `GetHashCode()` implementations is that they must return the same value for the lifetime of an object. An implementation based on mutable state is invalid and will cause really horrible-to-diagnose bugs. – Paul Turner Jan 28 '14 at 11:43
3

@Tragedian: The fundamental requirement is that `GetHashCode` must mirror the behavior of `Equals`. If two objects may be equal at one moment but may later be unequal, or vice versa, then it is necessary to ensure that no references to such objects are exposed to anything which might change their state unexpectedly. It's unfortunate that there's nothing in the type system to indicate that. – supercat Jan 29 '14 at 00:01
2

@Tragedian: .NET does not have tooling to practically control mutation. It's not useful nor practical to require immutability, therefore - in general, you'll need to require data that is not mutated, rather than data that cannot be mutated. Of course, where `readonly` members are practical - by all means, use them - just don't expect that to be practical everywhere. – Eamon Nerbonne Jun 05 '14 at 12:59
11

I think the calculation should be wrapped with the `unchecked` keyword, like so: `unchecked(this.Foo.GetHashCode() * 17 + this.Bar.GetHashCode())`. The sum might be larger than int.MaxValue. – mortb Feb 14 '18 at 12:42
3

@mortb - It's my understanding that unchecked only applies when the overflow/underflow can be detected at compile time (i.e., the expression only contains constants). Expressions containing non-constant terms default to unchecked. – Quintus Apr 22 '19 at 17:34
6

@Quintus: I stand corrected. When assigning `Bar = int.MaxValue; Foo = "something"`, running the `GetHashCode()` function and not having the `unchecked` keyword, the code will run and produce a negative hashcode and not crash, so the `unchecked` keyword is not necessary – mortb Apr 23 '19 at 07:19
C# defaults to unchecked while VB.Net defaults to checked ([src](https://anthonydgreen.net/2019/02/12/exhausting-list-of-differences-between-vb-net-c/#36)) - but both can be overridden using a compiler flag, so to be 100% sure of your intent, it might be good practice to use the unchecked keyword anyway – Zac Faragher Oct 08 '19 at 01:26
3

I have question about this 17: why 17? – Eru Mar 12 '21 at 09:06
@svick this is common knowledge to any programmer and has no impact on how to implement equals and hashcode. These two methods should be based on whether two objects of the same class have the same value, not on some fear about hash sets. Your idea is better said as "immutable data produces fewer bugs, because ... ." It has nothing to do with the question at hand. – user904963 Dec 13 '21 at 20:39
2

@user904963 1. People have to learn "common knowledge" somewhere. If they're looking at this question, I think there is a decent chance they have not learned it yet. 2. The whole point of `GetHashCode` is working with hashes, so I think highlighting a common source of problems is useful. 3. The question is "Implementing GetHashCode correctly", so it is relevant. – svick Dec 13 '21 at 20:58
@svick The question is in reference to a good hashing function. It wasn't an elementary question about data structures. The actual answer is to use `HashCode.combine` since it's marked c#. – user904963 Dec 14 '21 at 04:58

Implementing GetHashCode correctly

1 Answers1

Linked

Related