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

Question

为什么字典的键必须是不可变的？我想要一个简单明了的理由，解释一下为什么在Python字典中，键会有这样的限制。

Answer 1

正如Fredrik Lundh在这里所说：

字典的哈希表实现是通过从键值计算出的哈希值来查找键。如果键是一个可变对象，它的值可能会改变，因此它的哈希值也会改变。但是，改变键对象的人并不知道这个对象正在作为字典的键使用，所以它无法在字典中移动这个条目。这样，当你尝试在字典中查找同一个对象时，就找不到它，因为它的哈希值已经不同了。如果你试图查找旧的值，也找不到，因为在那个哈希桶中找到的对象的值会不同。

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，有点紧张（可能是因为我们想吃hobnobs），所以我们想检查一下在打乱之后，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寸混音放在哪里了。这根本就行不通。

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

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

2 个回答

撰写回答