c# - Why should dictionary keys be immutable?

Question

Got a question about why they ask to use immutable objects as keys in a Dictionary.

The question actually got in my head when I recently used a dictionary (not for the very purpose of a Hash table apparently though) to place Xml Node objects as keys. I then updated the nodes several times during the usage.

So what does 'use immutable keys' really mean?

Answer 1

When you insert a key into a hash table, the hash table asks the key for its hash code, and remembers it along with the key itself and the associated value. When you later perform a lookup, the hash table asks the key you're looking for for its hash code, and can very quickly find all the keys in the table that have the same hash code.

That's all fine so long as the keys in the hash table keep the same hash code throughout their lives - but if they're mutable (and are mutated after being inserted into the hash table) then typically the hash code will change, at which point the entry will never be found when you search for it.

Of course, this only applies to mutations which affect equality. For example, if you hash a Person entity with a name and birthday, but for some reason only the name is used for equality (and thus only the name is used when computing the hash code) then you could insert a Person into a hash table as a key, change its birthday, and still be able to look it up again later with no problems.