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

Question

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

Answer 1

在我的计算机上，有一个/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']

嗯，滚刀。无论如何…现在我们已经有点混乱了words，我们变得有点偏执了（可能出于与渴望滚刀相同的原因），并且我们想检查word_lengths字典中的所有单词是否都正确。words我们混合在一起之后仍然存在：

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

好吧，我们到了那里，但是在我的机器上花了三分钟多的时间-至少有足够的时间吃几对美味的饼干。考虑一下，很明显为什么：我们有…

>>> len(words)
99171

…大约有十万个单词要检查，对于字典中的每个单词，Python都必须搜索我们混合的单词列表，直到找到匹配的单词。不一定总是要检查整个列表，但平均每次平均要写五万个单词（或列表的一半），总共50,000×100,000
= 5,000,000,000次测试。即使在这个奇迹般的技术时代，五十亿也是如此。

只是要绝对确定（我通常不那么偏执；通常我只是困了），让我们检查一下其他方法，并确保其中的所有words内容仍然在word_lengths：

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

喂什么 这次大约是十分之一秒！是什么赋予了？你吓到我了，伙计……嘿，我的饼干在哪里？我刚刚有他们，我敢肯定。

与可以按照任何旧顺序排列的列表不同（因此，确保其中有某个项目意味着依次检查每个项目，直到找到它为止），字典的效率更高。参加聚会的乐趣可能会减少，但是，嘿，让它负责音乐，一切都结束了，是吗？

字典的无情效率的秘诀在于，对于每个项目，字典都会根据其内容计算密钥的哈希值（实际上是整数），并使用该哈希值将项目存储在内存中的特定位置。然后，当您去寻找项目时，它会再次计算密钥内容的哈希值，对自己说：“好吧，"python"哈希到7036520087640895475…是的，我知道我必须把它放在哪里了”，然后笔直地走。找到正确的存储位置。因此这一次，它只需要执行十万次检查，而不是五十亿次。

这有点像将您所有的CD整齐地按字母顺序放在架子上，而不是将它们随机从箱中堆放在扬声器顶部。我告诉你，字典知道它在哪里。

但是要付出代价，词典才能将其保持在一起。还记得我说字典根据项目的内容计算哈希值吗？好吧，如果该内容发生更改会怎样？对于不可变的对象来说，这不是问题-
它们的内容 不能 更改-但是，根据定义，可变对象 可以
更改其内容，并且当它们更改时，它们的哈希（如果有的话）也将更改。很显然，这很酷，并不是每个人都希望将其放入盒子中，我明白了，但是如果哈希值发生了变化，字典就无法解决将其放置在什么地方的问题。

好像Joy Division将其名称更改为New Order，现在您不知道将“ Blue Monday”的那12英寸混音放到哪里。这根本行不通。

因此，词典有一个规则：如果您想成为一个关键， 那就不要改变 。