CODEWITHSUNDEEP
c#dictionarykeyimmutability
Vaibhav
Vaibhav

Reputation: 2557

Why should dictionary keys be immutable?

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?

Upvotes: 1

Views: 3008

Answers (3)

Guffa
Guffa

Reputation: 700910

The dictionary places the items in buckets based on the hash code of the key. If you add an item and then change its key, you can't find the item any more.

If you use the new key value to look for it, the dictionary will look in a different bucket, and if you use the old key value the dictionary will find the bucket where it is, but the key no longer matches.

Upvotes: 3

JaredPar
JaredPar

Reputation: 755587

Dictionary types are a mapping between a key and a value. The mapping will use various properties of the key to assign it a slot in the internal dictionary storage. In most cases it simple reduces the properties to an int value.

If a key changes over time then its properties could begin to map to a different index in the table. Hence the key would no longer be able to retrieve values it originally was mapped to in the table. Immutable types avoid this altogether because they can never change. Hence their mapping is consistent for all time

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1504162

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.

Upvotes: 12

Related Questions