1

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?

assylias
  • 321,522
  • 82
  • 660
  • 783
Vaibhav
  • 2,527
  • 1
  • 27
  • 31
  • See my answer to [this question](http://stackoverflow.com/questions/15370081/how-net-dictionary-implementation-works-with-mutable-objects/15370321#15370321) in which I describe the consequences of a mutable dictionary key in detail. – Servy Mar 15 '13 at 18:01
  • A `Dictionary` is a kind of hashing data structure. If you changed a key, but it still took up the same slot within the data structure, would the hashing break? – Kenneth K. Mar 15 '13 at 18:01
  • Did [this blog post](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CDMQFjAA&url=http%3A%2F%2Feffbot.org%2Fpyfaq%2Fwhy-must-dictionary-keys-be-immutable.htm&ei=UWJDUebSM7ih4AOdnYCgAg&usg=AFQjCNE0QR_ktmMqgnRxGdE5f2ymgLaehw&bvm=bv.43828540,d.dmg) with your exact question title with "must" for "should" not answer your question or come up in your search results? – djechlin Mar 15 '13 at 18:04
  • Ex: In a dramatically specific and wierd requirement, I implemented an IDictionary. I have tested it through a decent amount of test scenarios. The XmlNodes were added to and/or removed but it still didn't break. – Vaibhav Apr 25 '13 at 10:28

3 Answers3

12

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.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • 2
    Worth noting, that since `XMLNode` (the case in the question) doesn't override `Equals` or `GetHashCode`, its concept of equality is based on identity, and identity is inherently immutable. While such objects are more rarely useful as keys, they are safe as keys in those cases where it is indeed useful. – Jon Hanna Jan 27 '14 at 14:27
3

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.

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
1

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

JaredPar
  • 733,204
  • 149
  • 1,241
  • 1,454
  • In what cases would it not reduce the key to an `int` value? – Allon Guralnek Mar 15 '13 at 18:04
  • @AllonGuralnek if the dictionary was implemented as a binary search tree. In that implementation you only need to know relative order which doesn't necessarily have to be an `int` (although in the vast majority of cases it's done that way) – JaredPar Mar 15 '13 at 18:07
  • Oh you were talking in the general sense, whereas I thought you were talking about the implementations in the BCL. – Allon Guralnek Mar 15 '13 at 18:11
  • @AllonGuralnek correct. The original version of this question didn't specify a language / framework hence I tried to keep my answer general. – JaredPar Mar 15 '13 at 18:12