Why don't I ever have to override GetHashCode when using Dictionaries on personal classes?

Question

It always seems to just "work" without ever having to do anything.

The only thing I can think of is that each class has a hidden sort of static identifier that Object.GetHashCode uses. (also, does anyone know how Object.GetHashCode is implemented? I couldn't find it in the .NET Reflector)

I have never overridden GetHashCode but I was reading around and people say you only need to when overriding Equals and providing custom equality checking to your application so I guess I'm fine?

I'd still like to know how the magic works, though =P

For fun, this answer includes a link to the `GetHashCode` source code: http://stackoverflow.com/questions/720177/default-implementation-for-object-gethashcode/720196#720196 — Douglas, Sep 18 '11 at 17:28

score 3 · Accepted Answer · answered Sep 18 '11 at 17:20

It always seems to just "work" without ever having to do anything.

You didn't tell us if you're using value types or reference types for your keys.

If you're using value types, the default implementation of Equals and GetHashCode are okay (Equals checks if the fields are equals, and GetHashCode is based on the fields (not necessarily all of them!)). If you're using reference types, the default implementation of Equals and GetHashCode use reference equality, which may or may not be okay; it depends on what you're doing.

The only thing I can think of is that each class has a hidden sort of static identifier that Object.GetHashCode uses.

No. The default is a hash code based on the fields for a value type, and the reference for a reference type.

(also, does anyone know how Object.GetHashCode is implemented? I couldn't find it in the .NET Reflector)

It's an implementation detail that you should never ever need to know, and never ever rely on it. It could change on you at any moment.

I have never overridden GetHashCode but I was reading around and people say you only need to when overriding Equals and providing custom equality checking to your application so I guess I'm fine?

Well, is default equality okay for you? If not, override Equals and GetHashCode or implmenet IEqualityComparer<T> for your T.

I'd still like to know how the magic works, though =P

Every object has Equals and GetHashCode. The default implementations are as follows:

For value types, Equals is value equality.
For reference types, Equals is reference equality.
For value types, GetHashCode is based on the fields (again, not necessarily all of them!).
For reference types, GetHashCode is based on the reference.

If you use a overload of Dictionary constructor that doesn't take a IEqualityComparer<T> for your T, it will use EqualityComparer<T>.Default. This IEqualityComparer<T> just uses Equals and GetHashCode. So, if you haven't overridden them, you get the implementations as defined above. If you override Equals and GetHashCode then this is what EqualityComparer<T>.Default will use.

Otherwise, pass a custom implementation of IEqualityComparer<T> to the constructor for Dictionary.

score 1 · Answer 2 · answered Sep 18 '11 at 17:07

Are you using your custom classes as keys or values? If you are using them only for values, then their GetHashCode doesn't matter.

If you are using them as keys, then the quality of the hash affects performance. The Dictionary stores a list of elements for each hash code, since the hash codes don't need to be unique. In the worst case scenario, if all of your keys end up having the same hash code, then the lookup time for the dictionary will like a list, O(n), instead of like a hash table, O(1).

The documentation for Object.GetHashCode is quite clear:

The default implementation of the GetHashCode method does not guarantee unique return values for different objects... Consequently, the default implementation of this method must not be used as a unique object identifier for hashing purposes.

score 0 · Answer 3 · answered Sep 18 '11 at 16:58

0

Object's implementations of Equals() and GetHashCode() (which you're inheriting) compare by reference.
Object.GetHashCode is implemented in native code; you can see it in the SSCLI (Rotor).

Two different instances of a class will (usually) have different hashcodes, even if their properties are equal.

You only need to override them if you want to compare by value – if you want to different instances with the same properties to compare equal.

answered Sep 18 '11 at 16:58

SLaks

868,454
176
1,908
1,964

1

That is not true that you only need to override hash code if you're comparing by value. Hash codes have nothing to do with comparing objects - it's a key for indexing into a hash table and the goal is to provide as little collisions as possible. – bryanmac Sep 18 '11 at 17:13
You can have a reference as a key in a dictionary in which case you can store several objects with the same values but with different identities or you can have values as key (in which case you have to override GetHashCode). But then you can store only one object with the same values. – Olivier Jacot-Descombes Sep 18 '11 at 17:22
Adding references (memory address keyed) into hash tables have caused horrible performance and "leaks" on real projects. For example, lookup a user externally (db, AD etc...) and add them to a hash table. Then later in code do the same on the same logical item. The table keeps growing and your "cache" never gets a hit ... Just be careful adding refs to dictionaries and test for what you expect :) – bryanmac Sep 18 '11 at 17:35
@bryan: Before you can talk about collisions, you need to define equality. That's what I mean by comparing. – SLaks Sep 18 '11 at 17:51
The collision is on the GetHashCode int % hash table array size. I'm referring to using the object as the key in a dictionary. Internally, that's how the dictionary handles non-unique hash code int collisions - it chains them. When it goes down the chain, if looks for reference equality. – bryanmac Sep 19 '11 at 01:46
@bryan: No; it calls `Equals`. If you haven't overridden `Equals()`, it will use reference equality. – SLaks Sep 19 '11 at 01:52

score 0 · Answer 4 · answered Sep 18 '11 at 17:01

It really depends on your definition of Equality.

class Person
{
    public string Name {get; set;}
}

void Test()
{
    var joe1 = new Person {Name="Joe"};
    var joe2 = new Person {Name="Joe"};

    Assert.AreNotEqual(joe1, joe2);
}

If you have a different definition for equality, you should override Equals & GetHashCode to get the appropriate behavior.

score 0 · Answer 5 · answered Sep 18 '11 at 17:22

Hash codes are for optimizing lookup performance in hash tables (dictionaries). While hash codes have a goal of colliding as little as possible between instances of objects they are not guaranteed to be unique. The goal should be equal distribution among the int range given a set of typical types of those objects.

The way hash tables work is each object implements a function to compute a hash code hopefully as distributed as possible amongst the int range. Two different objects can produce the same hash code but an instance of an object given it's data should always product the same hash code. Therefore, they are not unique and should not be used for equality. The hash table allocates an array of size n (much smaller than the int range) and when an object is added to the hash table, it calls GetHashCode and then it's mod'd (%) against the size of the array allocated. For collisions in the table, typically a list of objects is chained. Since computing hash codes should be very fast, a lookup is fast - jump to the array offset and walk the chain. The larger the array (more memory), the less collisions and the faster the lookup.

Objects GetHashCode cannot possibly produce a good hash code because by definition it knows nothing about the concrete object that's inheriting from it. That's why if you have custom objects that need to be placed in dictionaries and you want to optimize the lookups (control creating an even distribution with minimal collisions), you should override GetHashCode.

If you need to compare two items, then override equals. If you need the object to be sortable (which is needed for sorted lists) then override IComparable.

Hope that helps explain the difference.

Why don't I ever have to override GetHashCode when using Dictionaries on personal classes?

5 Answers5