为什么字典键必须是不可变的？

Question

为什么字典键必须是不可变的？我正在寻找一个简单、明确的原因，为什么Python字典中的键有这个限制。

Answer 1

作为弗雷德里克·隆德states here：

The hash table implementation of dictionaries uses a hash value calculated from the key value to find the key. If the key were a mutable object, its value could change, and thus its hash could also change. But since whoever changes the key object can’t tell that it was being used as a dictionary key, it can’t move the entry around in the dictionary. Then, when you try to look up the same object in the dictionary it won’t be found because its hash value is different. If you tried to look up the old value it wouldn’t be found either, because the value of the object found in that hash bin would be different.

Answer 2

在我的计算机上，有一个文件/etc/dictionaries-common/words包含大量英语单词：

>>> with open("/etc/dictionaries-common/words") as f:
...     words = [line.strip() for line in f]
... 
>>> "python" in words
True
>>> "BDFL" in words
False

让我们创建一个字典来存储所有这些单词的长度：

>>> word_lengths = {w: len(w) for w in words}
>>> word_lengths["parrot"]
6

为了好玩，我们将重新整理原始单词列表：

>>> from random import shuffle
>>> shuffle(words)
>>> words[:5]
["Willie's", 'Araceli', 'accessed', 'engagingly', 'hobnobs']

嗯，hobnobs。不管怎样。。。既然我们已经把words搞得一团糟，我们就变得有点偏执了（可能是因为我们渴望流浪汉的原因），我们想检查一下我们的word_lengths字典中的所有单词在我们把它们混在一起之后是否还在words：

>>> all(w in words for w in word_lengths)
True

好吧，我们到了，但在我的机器上花了三分钟-至少有足够的时间多吃几块美味的饼干。想想看，很明显的原因是：我们。。。

>>> len(words)
99171

。。。将近十万个单词需要检查，对于字典中的每一个单词，Python都必须搜索我们的混合单词列表，直到找到匹配的单词。它并不总是需要检查整个列表，但平均每次要检查5万个单词（或列表的一半），总共要进行50000×100000=5000000000个测试。即使在这个神奇的科技时代，50亿也是一大笔钱。

为了绝对确定（我通常不是那么多疑；通常我只是困了），让我们反过来检查一下，确保words中的所有内容仍然在word_lengths：

>>> all(w in word_lengths for w in words)
True

嘿，什么？这一次，大概是，十分之一秒！给什么？你吓到我了，伙计。。。嘿，我的饼干呢？我刚才有，我肯定。

与列表不同，它可以按任何旧的顺序排列（因此确保某个项在其中意味着依次检查每个项，直到我们找到它），字典的效率要高一些。也许在派对上没那么好玩，但是嘿，让它来负责音乐，一切都很有趣，你知道吗？

字典无情效率的秘诀是，对于每一个项，字典都会根据其内容计算密钥的哈希值（实际上是一个整数），并使用它将项存储在内存中的特定位置。然后，当你去寻找项目时，它会再次计算键内容的散列，对自己说“好的，"python"，散列到7036520087640895475。。。是的，我知道我一定把它放在哪里了“，然后直接去正确的记忆位置找到它。所以这次，它只需要做10万张支票，而不是50亿。

这有点像把你所有的CD整齐地按字母顺序放在架子上，而不是把它们随意地放在扬声器上。我告诉你，词典知道在哪儿。

但是，要想让词典保持一致，就得付出代价。还记得我说过字典根据项目的内容计算哈希值吗？好吧，如果内容改变了怎么办？对于不存在问题的不可变对象，其内容不能更改，但根据定义，可以更改其内容，当更改时，其散列（如果它们甚至有散列）也将更改。很酷，显然，不是每个人都想被放进盒子里，我明白了，但是如果杂凑变了，字典就没办法找出放东西的地方。

就好像Joy Division把他们的名字改成了新订单，现在你不知道你把那个12英寸的蓝色星期一混音放在哪里了。只是行不通。

所以，字典有一个规则：如果你想成为一个键，就不要去改变。