Clever Geek Handbook

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

Simple redefinition Equals

in TKey

does not help.

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

... Equals()

will never be called ...

+2


source to share


3 answers


When you do a dictionary search, this is the order of things:

  • The dictionary uses TKey.GetHashCode to compute the hash for the bucket.
  • It then checks all the hashes with this bucket and calls Equals on the individual objects to determine the match.

If the buckets never match (because GetHashCode was not overwritten), you will never call Equals. This is part of why you should always implement both if you do - and you should override both functions (more meaningful than just calling base.GetHashCode ()) if you want to use your object in a hashed collection.



If you implement the class, you must implement the GetHashCode procedure, which returns the same hash code for elements that are equal. Ideally, you want to return a different hash code for items that are not equal if possible, as this will greatly speed up dictionary lookups.

You should also use Equals in such a way as to correctly test for equal instances.

The default implementation for classes (reference types) simply compares the reference itself. Two instances with exactly the same values, returning false to Equals (since they have different references) by default. Multiple instances will always return a different default hash.

+7


source


Assuming you have defined a reference type as the key, you must either:

  • always passes the same object instance to the dictionary as a key, or
  • implement GetHashCode (), which always returns the same value even for different instances, and the Equals () method can compare different instances.

The base.GetHashCode () method builds a hash based on the object instance id and therefore cannot be used as a key when passed in different instances of a type.

The reason it always returns 0 for your hash is because the Dictionary class first uses the hashcode to find the bucket your key belongs to, and only then uses the Equals () method to distinguish between instances. You shouldn't return 0 as a hash code from a custom type if you intend to use it as a dictionary key, because that would effectively degenerate the dictionary into a list with an O (n) search function instead of O (1).



You can also consider implementing IComparable and IEquatable.

Take a look at the following question for more information:

Using an object as a public key for a dictionary

+1


source


A dictionary is a hash table. It only calls Equals (object obj) if two objects generate the same hash value. Provide a nice hash function for your objects to avoid calling Equals ().

Keep in mind that the hashing part is O (1) and the search part is O (n) in worst case and O (n / 2) in average. You should avoid objects that generate the same hash value, otherwise these objects will look linear

+1


source






More articles:


All Articles