When does Dictionary<TKey, TValue> call TKey.Equals() for custom TKey types?

Question

Just overriding Equals in TKey does not help.

public override bool Equals(object obj)
{ /* ... */  }

... Equals will never be called ...

... adding this doesn't help too:

public override int GetHashCode()
{
    return base.GetHashCode();
}

BUT, this helps:

public override int GetHashCode()
{
    return 0;
}

Now, I can look up keys in my dictionary.

WTF is going on?

Answer 1

Assuming you've defined a custom reference type as a key, you must either:

1. always pass the same object instance into a dictionary as a key, or
2. implement a GetHashCode() that always returns the same value even for different instances and an Equals() method can can compare different instances.

The base.GetHashCode() method build the hash based on the instance identity of the object and so cannot be used when you pass in different instances of a type as a key.

The reason that returning 0 for your hash always works, is that the Dictionary class first uses the hash code to look for the bucket your key belongs to, and only then uses the Equals() method to distinguish instances. You should not return 0 as a hash code from a custom type if you intend to use it as a dictionary key because that will effectively degenerate the dictionary into a list with O(n) lookup performance instead of O(1).

You may also want to consider implement IComparable and IEquatable.

Look at the following question for more details:

http://stackoverflow.com/questions/634826/using-an-object-as-a-generic-dictionary-key-in-net

Answer 2

When you do a dictionary lookup, this is the order things happen:

1. The dictionary uses TKey.GetHashCode to compute a hash for the bucket.
2. It then checks all of the hashes using that bucket, and calls Equals on the individual objects, to determine a match.

If the buckets never match (because GetHashCode wasn't overwritten), then you'll never call Equals. This is part of why you should always implement both if you implement either - and you should override both functions (more meaningfully than just calling base.GetHashCode()) if you want to use your object in a hashed collection.

If you're implementing a class, you should implement a GetHashCode routine that returns the same hash code for items that are Equal. Ideally, you want to return a different hash code for items that are not equal whenever possible, as this will make your dictionary lookups much faster.

You should also implement Equals in a way that checks for equal instances correctly.

The default implementation for classes (reference types) just compare the reference itself. Two instances, with exactly the same values, with return false on Equals (since they have different references), by default. Multiple instances will always also return a different hash code, by default.

Answer 3

Dictionary is a Hash Table. It only calls Equals(object obj) if two objects produces the same hash values. Provide a good hash function for your objects to avoid calling Equals().

Keep in mind that the Hashing part has the complexity O(1) and the search part has the complexity O(n) in worst case and O(n/2) in average case. You should avoid objects that generate the same hash value, otherwise this objects are searched linear