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

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']

嗯,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

嘿,什么？这次是十分之一秒!是什么赋予了？你吓坏我了,伙计......嘿,我的饼干在哪里？我刚才有他们,我很确定.

与列表不同,列表可以是任何旧的顺序(因此确保某些项目在那里意味着依次检查每个项目,直到我们找到它),字典更有效.在聚会上可能不那么有趣,但嘿,让它掌控音乐,所有都是copacetic,你知道吗？

字典无情效率的秘诀在于,对于每个项目,字典根据其内容计算密钥的哈希(实际上只是一个整数),并使用它来将项目存储在内存中的特定位置.然后,当你去寻找项目时,它会再次计算密钥内容的哈希值,对自己说"好吧"python",那哈希到7036520087640895475......是的,我知道我必须把它放在那里,然后",然后直截了当到正确的内存位置找到它.所以这一次,它只需要进行十万次检查,而不是五十亿次.

这有点像把所有的CD整齐地放在架子上,而不是随机堆叠在扬声器顶部.我告诉你,字典知道它在哪里.

但是要为字典保持整合的能力付出代价.还记得当我说字典根据项目的内容计算哈希值时吗？那么,如果内容发生变化会发生什么？对于不成问题的不可变对象 - 它们的内容不能改变 - 但是根据定义,可变对象可以改变它们的内容,当它们这样做时,它们的哈希(如果它们甚至有一个)也会改变.这很酷,很明显,并不是每个人都想放在一个盒子里,我明白了,但是如果哈希发生了变化,那么字典就无法解决它所放置的问题.

好像Joy Division将他们的名字改为New Order,现在你已经不知道在哪里放了12"混合蓝色星期一.它只是不会起作用.

所以,词典有一条规则:如果你想成为一把钥匙,就不要改变.

Answer 2

正如 Fredrik Lundh所说：

字典的哈希表实现使用从键值计算的哈希值来查找键。如果键是一个可变对象，它的值可能会改变，因此它的哈希值也可能会改变。但是由于更改键对象的人无法判断它被用作字典键，因此它无法在字典中移动条目。然后，当您尝试在字典中查找相同的对象时，将找不到它，因为它的哈希值不同。如果您尝试查找旧值，也不会找到它，因为在该散列箱中找到的对象的值会有所不同。