C# Dictionary<> and mutable keys

Question

I was told that one of the many reasons strings were made immutable in the C# spec was to avoid the issue of HashTables having keys changed when references to the string keys altered their content.

The Dictionary<> type allows reference types to be used as a key. How does the dictionary avoid the issue of altered keys that lead to "misplaced" values? Is there a memberwise clone made of an object when used as a key?

Answer 1

The Dictionary<> class does nothing to protect itself against a mutable key object being changed. It's up to you to know whether or not the class you're using as a key is mutable, and to avoid it if possible.

Answer 2

The Dictionary<TKey,TValue> type makes no attempt to protect against the user modifying the key used. It is purely left up to the developer to be responsible in not mutating the key.

If you think about this a bit this is really the only sane route that Dictionary<TKey,TValue> can take. Consider the implication of doing an operation like a memberwise clone on the object. In order to be thorough you'd need to do a deep clone because it will be possible for an object referenced in the key to also be mutated and hence affect the hash code. So now every key used in the table has it's full object graph cloned in order to protect against mutation. This would be both buggy and possibly a very expensive operation.

Answer 3

It does not avoid this situation. It's up to the calling code to enforce this:

As long as an object is used as a key in the Dictionary<TKey, TValue>, it must not change in any way that affects its hash value. Every key in a Dictionary<TKey, TValue> must be unique according to the dictionary's equality comparer. A key cannot be null, but a value can be, if the value type TValue is a reference type.

(From MSDN)

Answer 4

If you're using a mutable reference type as a key, the default implementation of GetHashCode() will guarantee hash equality regardless of object state (i.e. the hash is tied to the reference, not the state). You're correct, however, that a mutable type with value equality semantics (where GetHashCode presumably depends on state) is a bad choice for a dictionary key.