为什么我不能在python中使用列表作为dict键？

Question

关于什么可以/不能用作python dict的键,我有点困惑.

dicked = {}
dicked[None] = 'foo'     # None ok
dicked[(1,3)] = 'baz'    # tuple ok
import sys
dicked[sys] = 'bar'      # wow, even a module is ok !
dicked[(1,[3])] = 'qux'  # oops, not allowed

所以一个元组是一个不可变的类型,但是如果我在其中隐藏一个列表,那么它就不能成为一个键......难道我不能轻易地隐藏模块中的列表吗？

我有一个模糊的想法,关键是必须"可以",但我只是承认自己对技术细节的无知; 我不知道这里到底发生了什么.如果您尝试使用列表作为键,将哈希作为其内存位置,会出现什么问题？

Answer 1

为什么我不能在python中使用列表作为dict键？

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

(对于任何偶然发现这个问题寻找方法的人)

正如其他人在这里解释的那样,确实你不能.但是,如果您真的想使用列表,则可以使用其字符串表示.

Answer 2

在Python维基中有一篇关于这个主题的好文章:为什么列表不能是字典键.如上所述:

如果您尝试使用列表作为键,将哈希作为其内存位置,会出现什么问题？

它可以在不破坏任何要求的情况下完成,但会导致意外行为.列表通常被视为其值来自其内容的值,例如在检查(in-)相等时.许多人 - 可以理解 - 希望你可以使用任何列表[1, 2]来获得相同的密钥,在那里你必须保持完全相同的列表对象.但是,一旦用作密钥的列表被修改,就会通过值中断查找,并且对于按身份查找,需要您保持完全相同的列表 - 这对于任何其他常见列表操作都是不需要的(至少我无法想到).

其他对象,比如模块,object无论如何都要从它们的对象身份中做出更大的交易(当你最后一次调用两个不同的模块对象时sys？),并且无论如何都会进行比较.因此,当用作字典键时,它们在这种情况下通过身份进行比较也就不那么令人惊讶 - 甚至是预期的.

Answer 3

问题是元组是不可变的,而列表则不是.考虑以下

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

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

最终,没有令人满意的答案.例如,如果唯一有效的密钥是原始密钥,那么如果您没有引用该密钥,则永远不能再次访问该值.使用其他所有允许的密钥,您可以构建密钥而无需引用原始密钥.

如果我的两个建议都有效,那么你有非常不同的键返回相同的值,这有点令人惊讶.如果只有原始内容有效,那么您的密钥将很快变坏,因为要对列表进行修改.

Answer 4

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

如果您尝试使用列表作为键,将哈希作为其内存位置,会出现什么问题？

查找具有相同内容的不同列表将产生不同的结果,即使比较具有相同内容的列表将指示它们是等效的.

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

Answer 5

刚发现您可以将List更改为元组,然后将其用作键.

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

Answer 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

在 mutating 之后stupid，它在字典中再也找不到了，因为哈希值改变了。只有对 dict 的键列表进行线性扫描才能找到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

这也不是一个好主意，因为相等的对象应该具有相同的哈希值，以便您可以在 adict或 中找到它们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

事情似乎按预期工作，但想想发生了什么：当您的类的所有实例产生相同的哈希值时，只要有两个以上的实例作为 a 中的键dict或存在于 a 中，就会发生哈希冲突set。

使用my_dict[key]or key in my_dict(or item in my_set)找到正确的实例需要执行stupidlist3与 dict 键中的实例一样多的相等性检查（在最坏的情况下）。在这一点上，字典的目的——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键，因为元组是不可变和可散列的。