CODEWITHSUNDEEP
c#.netdictionary
anon
anon

Reputation:

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

Just overriding Equals in TKey does not help.

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

... Equals() will never be called ...

Upvotes: 2

Views: 2129

Answers (3)

LBushkin
LBushkin

Reputation: 131696

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:

Using an object as a generic Dictionary key

Upvotes: 1

Thomas Maierhofer
Thomas Maierhofer

Reputation: 2681

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

Upvotes: 1

Reed Copsey
Reed Copsey

Reputation: 564433

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.

Upvotes: 8

Related Questions