Does the Dictionary created by the default constructor use a hash code?

Question

I need to use the class that I wrote as the key type for Dictionary

I read the documentation on MSDN about the default constructor Dictionary

Dictionary<TKey, TValue> requires an equality implementation to determine if the keys are the same. This constructor uses the default common equality divisor, EqualityComparer<T>.Default . If the TKey type implements the common System.IEquatable<T> interface, the equality TKey uses this implementation by default. Alternatively, you can specify an implementation of the IEqualityComparer<T> generic interface using a constructor that accepts a comparison parameter.

This makes me think that the only thing I need to do is to have a class for the key tool System.IEquatable<T>

However, I am very surprised that System.IEquatable<T> does not have a HashCode() method.

So will the Dictionary created in this way use a hash code? If so, where did it come from? Otherwise, my dictionary will have operations with constant access to value (I do not think that this is possible without a hash code)

Answer 1

It still uses the overridden object.GetHashCode() method to get the hash code. The reason is that there is a separate IEquatable<T> interface (i.e. why, by default, EqualityComparer<T> does not always just call the overridden object.Equals() method to compare two objects) for performance reasons - object.Equals() accepts the object argument, and therefore the implementation must pass it to the target type before it can make a meaningful comparison (value types must also be in the box and unpacked); whereas the argument IEquatable<T>.Equals() already has type T This performance consideration does not apply to the GetHashCode() method, since it does not accept an argument, so there is no reason for it to exist in the IEquatable<T> interface.

Answer 2

However, I am very surprised that System.IEquatable does not have a HashCode () method.

For System.IEquatable<T> it would be superfluous to use the HashCode method as System.Object (which your implementation class implicitly inherits from) already provides the GetHashCode method

Answer 3

Yes, the dictionary will use a hash code. The dictionary really is a hash map under covers.

The hash implementation that it will use is the one implemented in GetHashCode in your key. If you do not define the implementation yourself, the hash code will be based on the link for reference types and on separate fields for value types (structs). When using your own class as a key in a dictionary, it is recommended that you implement GetHashCode .

When you implement IEquatable<T> , you must override Equals and GetHashCode on the object according to your implementation of IEquatable<T> . The reason this is not in the interface is because GetHashCode already defined on the object from which all classes derive, so having it in the interface will not make any difference.

If you do not implement GetHashCode , so it matches your IEquatable<T> implementation, you may encounter a problem when you put the key in the dictionary, but you cannot get it again because the hash code does not match: When the dictionary looks for the key, it first calls GetHashCode on this key. From this dictionary, an internal bucket is derived, which should be the key. He then scans all the keys in this particular bucket and calls Equals to find the correct key.

Answer 4

Dictionary (HashSet and KeyedCollections) uses HashBuckets (for speed).
HashBuckets uses GetHashCode, which is Int32.

If the objects are not equal, then they must have different GetHashCode.
But two objects that are not equal can have the same GetHashCode.

If the GetHashCode code is the same, then the tie-breaker is equal to Equals.
GetHashCode comparison is faster - you want to avoid decoupling.

You need a good (unique) GetHashCode.
If the objects come from the database, and the table has a key and the key has Int32 (or less), then use this for the perfect hash code.

If your objects do not have a natural key, then you can use the GetHashCode system.
But if you have a natural key, use it.

Object Object Object Class
If your class does not override GetHashCode, it will be created from Object.

Consult against Tuple or KeyValuePair for Key as they do not create a good GetHashCode. Lots of collisions.