为什么我不能在 python 中使用 list 作为 dictkey？

我有点困惑，什么可以/不能被用作一个巨蟒的关键字。

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

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

我有一些模糊的想法，关键必须是“散列”，但我只是要承认我自己对技术细节的无知; 我不知道这里到底发生了什么。如果您试图使用列表作为键，使用散列作为它们的内存位置，那么会出现什么问题呢？

158179 次浏览
小开

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

如果您试图使用列表作为键，使用散列作为它们的内存位置，那么会出现什么问题呢？

查找具有相同内容的不同列表将产生不同的结果，尽管对具有相同内容的列表进行比较将表明它们是等价的。

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

小开

问题在于元组是不可变的，而列表不是

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

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

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

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

小开
最佳答案

Python wiki 中有一篇关于这个主题的好文章: 为什么列表不能是字典键:

如果您试图使用列表作为键，使用散列作为它们的内存位置，那么会出现什么问题呢？

它可以在不违反任何需求的情况下完成，但是它会导致意外的行为。列表通常被视为其值是从其内容的值派生而来的，例如在检查(in -)相等性时。可以理解的是，许多人希望您可以使用任何列表 [1, 2]来获得相同的键，在这种情况下必须保持完全相同的列表对象。但是，一旦用作键的列表被修改，按值查找就会中断，而按身份查找则需要保持完全相同的列表——这对于任何其他常见的列表操作都是不需要的(至少我能想到的没有)。

其他对象，比如模块和 object，对它们的对象标识做了更大的贡献(上次有两个不同的模块对象称为 sys是什么时候?)无论如何都会被拿来比较。因此，在这种情况下，当它们被用作 dictkey 时，通过身份进行比较就不那么令人惊讶了，甚至不那么令人期待了。

小开

你的答案可以在这里找到:

为什么列表不能是字典键

初学 Python 的人经常想知道为什么，而 Python 语言同时包含了这两种语言 元组和列表类型，元组可用作字典键，而 这是一个经过深思熟虑的设计决定，而且最好是 通过首先理解 Python 字典的工作原理来解释。

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

小开

根据 Python 2.7.2文档:

如果一个对象有一个从不改变的散列值，那么它是可散列的 在其生存期内(它需要 __hash__()方法) ，并且可以 与其他对象相比(它需要一个 __eq__()或 __cmp__()方法)。 比较相等的可散列对象必须具有相同的散列值。

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

Python 所有不可变的内置对象都是散列的，而不是 可变容器(如列表或字典)是 默认情况下，用户定义类的实例是散列的; 它们的散列值都是 id()。

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

对列表散列使用 id 将意味着所有列表的比较方式不同，这将是令人惊讶和不方便的。

小开

对于您的问题，简单的答案是类列表没有实现任何希望在字典中用作键的对象所需的方法 大麻。然而，为什么 大麻没有像元组类(基于容器的内容)那样实现，是因为列表是可变的，所以编辑列表需要重新计算散列，这可能意味着列表现在位于下哈希表的错误桶中。注意，由于您不能修改 tuple (不可变的) ，所以不会遇到这个问题。

顺便说一句，字母对象查找的实际实现是基于 Knuth Vol. 3，Sec. 6.4中的算法 D。如果你有这本书，它可能是一本值得一读的书，除此之外，如果你真的非常非常感兴趣，你可能会想看一看开发人员对实际 单词对象的实现。的评论。它详细介绍了它是如何工作的。还有一个关于字典实现的 巨蟒讲座，您可能会感兴趣。他们在开始的几分钟内讨论了键的定义以及散列是什么。

小开

为什么我不能在 python 中使用 list 作为 dictkey？

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

(对于那些无意中发现这个问题并试图绕过它的人)

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

小开

刚刚发现你可以把 List 变成 tuple，然后用它作为键。

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

因为列表是可变的，所以 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之后，由于散列发生了更改，因此不能再在 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

这也不是一个好主意，因为相等的对象应该散列相同，以便您可以在 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中或者在 set中出现，你就会发生散列冲突。

使用 my_dict[key]或 key in my_dict(或 item in my_set)查找正确的实例需要执行尽可能多的相等性检查，因为在 dict 的键中有 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)。

DR: 您可以使用 tuple(yourlist)作为 dict键，因为元组是不可变的和散列的。

小开

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

类似(psuedo 代码)的东西:

{key : val}
hash(key) = val

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

任何 < strong > hashable (可以转换为 hash，并保持静态值即不可变，从而使 如上所述的散列键) 符合条件，但 因为列表或设置对象可以随着时间的推移而变化，所以哈希(键)也应该需要变化，只是为了与列表或设置同步。

你可以试试:

hash(<your key here>)

如果它工作良好，它可以作为关键字为您的字典或转换为某些散列。

简而言之:

  1. 将该列表转换为 tuple(<your list>)。
  2. 将该列表转换为 str(<your list>)。
小开

很简单，我们可以记住，dict键需要是 永恒不变(确切地说，散列的)。列表是可变的(确切地说，列表不提供有效的 __hash__方法)。

在这里，不可变物件(不可更改的对象)是一个对象，其状态在创建后不能被修改。这与可变对象(可变对象)形成对比，可变对象在创建后可以进行修改。


提交答案