124

我对什么可以/不能用作 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

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

我有一些模糊的想法，即密钥必须是“可散列的”，但我承认我自己对技术细节的无知；我不知道这里到底发生了什么。如果您尝试将列表用作键，而将哈希用作它们的内存位置，会出现什么问题？

4

11 回答 11

47

Python wiki 中有一篇关于该主题的好文章：Why Lists Can't Be Dictionary Keys。正如那里解释的那样：

如果您尝试将列表用作键，而将哈希用作它们的内存位置，会出现什么问题？

它可以在不真正破坏任何要求的情况下完成，但它会导致意外行为。列表通常被视为其值源自其内容的值，例如在检查（不）相等性时。许多人会 - 可以理解 - 期望您可以使用任何列表[1, 2]来获取相同的键，而您必须保持完全相同的列表对象。但是，一旦用作键的列表被修改，按值查找就会中断，并且对于按标识查找要求您保持完全相同的列表 - 这对于任何其他常见的列表操作都不是必需的（至少我想不到）。

其他对象，例如模块，object无论如何都会从它们的对象标识中做出更大的交易（你最后一次拥有两个不同的模块对象是什么时候sys？），无论如何都要进行比较。因此，当它们用作字典键时，在这种情况下也会按身份进行比较，这并不令人惊讶 - 甚至是预期的。

于 2011-08-31T13:36:23.740 回答
44

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

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

（对于任何偶然发现这个问题并寻找解决方法的人）

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

于 2011-08-31T13:55:05.080 回答
34

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

d = {tuple([1,2,3]): 'value'}
于 2018-08-02T18:44:59.600 回答
18

问题是元组是不可变的，而列表不是。考虑以下

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

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

最终，没有令人满意的答案。例如，如果唯一有效的键是原始键，那么如果您没有引用该键，您将永远无法再次访问该值。对于所有其他允许的密钥，您可以构造一个不引用原始密钥的密钥。

如果我的两个建议都有效，那么您有非常​​不同的键返回相同的值，这有点令人惊讶。如果只有原始内容有效，那么您的密钥很快就会变坏，因为列表是用来修改的。

于 2011-08-31T13:32:58.033 回答
9

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

如果您尝试将列表用作键，而将哈希用作它们的内存位置，会出现什么问题？

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

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

于 2011-08-31T13:31:07.260 回答
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，因为哈希值改变了，所以在字典中找不到了。只有对字典的键列表进行线性扫描才能找到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（在最坏的情况下）。在这一点上，字典的目的——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键，因为元组是不可变的和可散列的。

于 2018-10-25T22:18:24.837 回答
3

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

附带说明一下，dictobjects 查找的实际实现是基于 Knuth Vol. 中的算法 D。3，秒。6.4. 如果您有这本书可供您使用，那么它可能值得一读，此外，如果您真的非常感兴趣，您可能想在这里查看开发人员对 dictobject 实际实现的评论。它详细介绍了它的工作原理。还有一个关于字典实现的Python 讲座，您可能会感兴趣。它们在最初几分钟内介绍了键的定义以及哈希是什么。

于 2011-08-31T13:54:20.673 回答
3

您可以在此处找到您的遮阳篷：

为什么列表不能是字典键

Python 的新手经常想知道为什么虽然该语言同时包含元组和列表类型，但元组可用作字典键，而列表则不能。这是一个深思熟虑的设计决定，最好通过首先了解 Python 字典的工作原理来解释。

来源和更多信息：http ://wiki.python.org/moin/DictionaryKeys

于 2011-08-31T13:36:57.053 回答
-1

根据 Python 2.7.2 文档：

如果一个对象的哈希值在其生命周期内永远不会改变（它需要一个__hash__()方法），并且可以与其他对象进行比较（它需要一个__eq__()or__cmp__()方法），那么它就是可哈希的。比较相等的可散列对象必须具有相同的散列值。

哈希性使对象可用作字典键和集合成员，因为这些数据结构在内部使用哈希值。

Python 的所有不可变内置对象都是可散列的，而没有可变容器（例如列表或字典）是可散列的。默认情况下，作为用户定义类实例的对象是可散列的；它们都比较不相等，它们的哈希值是它们的id().

元组是不可变的，你不能添加、删除或替换它的元素，但元素本身可能是可变的。List 的哈希值取决于其元素的哈希值，因此当您更改元素时它会发生变化。

将 id 用于列表哈希意味着所有列表比较不同，这会令人惊讶且不方便。

于 2011-08-31T13:44:11.937 回答
-1

Dictionary 是一个 HashMap，它存储您的键映射、转换为散列的新键和值映射的值。

类似（伪代码）：

{key : val}  
hash(key) = val

如果您想知道哪些可用选项可用作字典的键。然后

任何可散列的东西（可以转换为散列，并保持静态值，即不可变，以便生成如上所述的散列键）是合格的，但由于列表或集合对象可以随时变化，因此散列（键）也应该需要变化只是为了与您的列表或集合保持同步。

你可以试试 ：

hash(<your key here>)

如果它工作正常，它可以用作字典的键，或者将其转换为可散列的东西。

简而言之 ：

  1. 将该列表转换为tuple(<your list>).
  2. 将该列表转换为str(<your list>).
于 2020-03-19T04:03:14.177 回答
-1

简单地说，我们可以记住，dict密钥需要是不可变的（准确地说，是可散列的）。列表是可变的（确切地说，列表不提供有效的__hash__方法）。

这里的不可变对象（unchangeable object）是一个对象，其状态在创建后不能被修改。这与可变对象（changeable object）形成对比，可变对象在创建后可以修改。

于 2020-07-23T15:42:02.957 回答