为什么我不能在 python 中使用列表作为字典键？到底什么可以使用，什么不能使用，为什么？-IT科技

摘要：问题描述：我发现以下内容均有效：>>> d = {} >>> d[None] = 'foo' >>> d[(1, 3)] = 'baz' 甚至模块也可以用作字典键：>>> import sys >>> d[sys] = ...

问题描述：

我发现以下内容均有效：

>>> d = {}
>>> d[None] = 'foo'
>>> d[(1, 3)] = 'baz'

甚至模块也可以用作字典键：

>>> import sys
>>> d[sys] = 'bar'

但是，列表不能，包含列表的元组也不能：

>>> d[[2]] = 'spam'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> d[(1, [3])] = 'qux'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

为什么将列表存储在元组中意味着它不能再作为字典键？毕竟，我可以轻松地在模块内“隐藏”列表（事实上，例如sys.path已经是一个列表了）。

我模糊地认为键必须是“可哈希的”，但我不太清楚这意味着什么，或者为什么会有这样的限制。如果 Python 允许使用列表作为键，比如使用它们的内存位置作为哈希，会发生什么问题？

解决方案 1：

Python wiki 上有一篇关于该主题的好文章：为什么列表不能作为字典的键。正如那里所解释的：

如果 Python 允许使用列表作为键（比如使用它们的内存位置作为哈希），会发生什么问题？

这会导致一些意外行为。列表通常被视为其值来自其内容的值，例如在检查（不）相等时。许多人会 - 可以理解 - 期望您可以使用任何列表[1, 2]来获取相同的键，而您必须保留完全相同的列表对象。但是，一旦用作键的列表被修改，按值查找就会中断，而按身份查找需要跟踪该精确的列表对象 - 这不是使用列表的普通要求。

其他对象，例如模块和object，无论如何都会更重视其对象身份（您上次有两个不同的模块对象称为是什么时候sys？），并且无论如何都会通过身份进行比较。因此，当它们用作字典键时，在这种情况下也会通过身份进行比较，这并不令人惊讶 - 甚至在意料之中。

解决方案 2：

列表可以转换为元组，可用作字典键：例如

d = {tuple([1,2,3]): 'value'}

解决方案 3：

为什么不能在 Python 中使用列表作为字典的键？

>>> d = {repr([1,2,3]): 'value'}
{'[1, 2, 3]': 'value'}

正如其他人在这里所解释的那样，你确实不能。但是，如果你真的想使用列表，你可以使用它的字符串表示形式。

解决方案 4：

问题在于元组是不可变的，而列表不是。考虑这个例子：

d = {}
li = [1,2,3]
d[li] = 5
li.append(4)

应该返回什么d[li]？是同一个列表吗？怎么样d[[1,2,3]]？它具有相同的值，但它是不同的列表吗？

最终，没有令人满意的答案：

如果唯一有效的键是原始键，那么如果不保留对原始键的引用（并访问它），就无法访问该值
如果只有具有相同内容的键才有效，则修改该键会改变查找的工作方式；并且任何引用该列表的其他代码都可能对其进行修改，从而可能在以后引起意外。
如果两者都有效，那么您就有非常不同的键映射到相同的值，这是有点令人惊讶的。

解决方案 5：

这是一个答案http://wiki.python.org/moin/DictionaryKeys

如果您尝试使用列表作为键，并使用哈希作为其内存位置，会发生什么问题？

查找具有相同内容的不同列表会产生不同的结果，即使比较具有相同内容的列表会表明它们是等效的。

在字典查找中使用列表文字怎么样？

解决方案 6：

因为列表是可变的，所以dict键（和set成员）需要可哈希，而对可变对象进行哈希处理不是一个好主意，因为哈希值应该根据实例属性来计算。

set在这个答案中，我将给出一些具体的例子，希望能够在现有答案的基础上增加价值。每个见解也适用于数据结构的元素。

示例 1：对可变对象进行散列，其中散列值基于对象的可变特性。

>>> class stupidlist(list):
...     def __hash__(self):
...         return len(self)
... 
>>> stupid = stupidlist([1, 2, 3])
>>> d = {stupid: 0}
>>> stupid.append(4)
>>> stupid
[1, 2, 3, 4]
>>> d
{[1, 2, 3, 4]: 0}
>>> stupid in d
False
>>> stupid in d.keys()
False
>>> stupid in list(d.keys())
True

改变之后stupid，由于哈希值已更改，因此无法再在字典中找到它。只有对字典的键列表进行线性扫描才能找到stupid。

示例 2：...但为什么不只是一个常量哈希值？

>>> class stupidlist2(list):
...     def __hash__(self):
...         return id(self)
... 
>>> stupidA = stupidlist2([1, 2, 3])
>>> stupidB = stupidlist2([1, 2, 3])
>>> 
>>> stupidA == stupidB
True
>>> stupidA in {stupidB: 0}
False

这也不是一个好主意，因为相等的对象应该具有相同的哈希值，以便您可以在dict或中找到它们set。

示例 3：... 好的，那么所有实例中的常量哈希值怎么样？！

>>> class stupidlist3(list):
...     def __hash__(self):
...         return 1
... 
>>> stupidC = stupidlist3([1, 2, 3])
>>> stupidD = stupidlist3([1, 2, 3])
>>> stupidE = stupidlist3([1, 2, 3, 4])
>>> 
>>> stupidC in {stupidD: 0}
True
>>> stupidC in {stupidE: 0}
False
>>> d = {stupidC: 0}
>>> stupidC.append(5)
>>> stupidC in d
True

dict事情似乎按预期进行，但请考虑一下正在发生的事情：当您的类的所有实例都产生相同的哈希值时，只要有两个以上的实例作为 a 中的键或 a 中存在，就会发生哈希冲突set。

要找到正确的实例，需要执行与my_dict[key]字典key in my_dict键中item in my_set的实例数一样多的相等性检查stupidlist3（在最坏的情况下）。此时，字典的目的 - O(1) 查找 - 完全失败了。以下时间演示了这一点（使用 IPython 完成）。

示例 3 的一些时间安排

>>> lists_list = [[i]  for i in range(1000)]
>>> stupidlists_set = {stupidlist3([i]) for i in range(1000)}
>>> tuples_set = {(i,) for i in range(1000)}
>>> l = [999]
>>> s = stupidlist3([999])
>>> t = (999,)
>>> 
>>> %timeit l in lists_list
25.5 µs ± 442 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit s in stupidlists_set
38.5 µs ± 61.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit t in tuples_set
77.6 ns ± 1.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

正如您所见，我们的成员资格测试stupidlists_set甚至比对整个进行线性扫描还要慢lists_list，而您在没有大量哈希冲突的集合中拥有预期的超快查找时间（因子 500）。

TL; DR：您可以将其用作tuple(yourlist)键dict，因为元组是不可变且可哈希的。

解决方案 7：

对你的问题的简单回答是，类列表没有实现方法hash，而该方法对于希望用作字典中的键的任何对象都是必需的。但是，之所以没有像在元组类中那样实现hash（基于容器的内容），是因为列表是可变的，因此编辑列表需要重新计算哈希，这可能意味着列表现在位于底层哈希表中的错误存储桶中。请注意，由于您无法修改元组（不可变），因此不会遇到此问题。

顺便提一下，dictobjects 查找的实际实现基于 Knuth 第 3 卷第 6.4 节中的算法 D。如果您有这本书，它可能值得一读，此外，如果您真的非常感兴趣，您可能想在这里查看开发人员对 dictobject 实际实现的评论。它详细介绍了它的工作原理。还有一个关于字典实现的Python 讲座，您可能会感兴趣。他们在前几分钟介绍了键的定义以及哈希是什么。