为什么列表不能作为字典的键？

Question

为什么列表不能作为字典的键？

4

我想要一个字典中的键是列表，定义如下：

data = { 
  [24,48,96]: ["QN.FN.EQ", "OT.AR.LN", "BL.VL.TR"] 
}

这个不起作用，错误提示为"列表类型不可哈希"。

有什么解决方法吗？以便像下面这样从字典中获取数据：

data[[24,48,96]] # => ["QN.FN.EQ", "OT.AR.LN", "BL.VL.TR"]

我现在唯一的解决方案是将列表转换为字符串，然后使用字符串作为键。

data = { 
  "24,48,96": ["QN.FN.EQ", "OT.AR.LN", "BL.VL.TR"] 
}
arr = [24,48,96]
print(data[','.join(map(str,arr))])

- BladeMight

1

键应该是不可变的，列表是可变的设计。请使用元组。 - Michael Butscher

6

请使用元组(24, 48, 96)，而非列表。 - cole

1

@Scott 不，我需要元组（tuple）！ - BladeMight

1

字典的工作原理是通过对键进行哈希（计算一个数字），并使用该哈希来决定在哪里存储键和值。哈希几乎总是基于对象的内容。因此，如果您将列表作为键，则它将根据其内容存储在特定位置。然后，如果列表发生变化，哈希值将发生变化。如果哈希值发生变化，则字典将查找错误的位置以检索您存储的值。这就是为什么Python不为列表提供__hash __()方法的原因。 - Steven Rumbalski

1

我稍微编辑了一下你的问题，[24,48,96] 是一个列表，而不是数组。这很重要，因为我们还有 numpy 数组、bytearray 和 array.array...（我还在我的答案中添加了一些时间）。 - timgeb

显示剩余2条评论

4个回答

5

你可以使用元组作为字典的键，例如：

data = { 
    (24,48,96): ["QN.FN.EQ", "OT.AR.LN", "BL.VL.TR"] 
}

print data[(24,48,96)]

- Felipe Ferri

很好，完全是我需要的！ - BladeMight

1

为什么Python字典无法接受数组作为键？

答案：因为在Python中，数组是一个可变的列表。可变的东西不能作为字典键使用。你只能使用不可变的东西，如字符串或元组作为键。

- Ijaz Ahmad

0

我认为在Python中不允许使用可变数据类型作为键。这就是为什么元组可以工作，但列表不行的原因。基本上，如果您可以原地更改数据，则无法将其用作键。

- mRotten

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- timgeb · Accepted Answer

我将回答这篇文章标题中的问题。因为列表是可变的，字典键需要是可哈希的，而哈希可变对象是一个坏主意，因为哈希值应该基于实例属性计算。下面是示例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 中作为键或在 set 中出现时，就会发生哈希冲突。

使用 d[key] 或 key in d 找到正确的实例需要执行与 stupidlist3 的实例数量相同的等式检查。此时，字典的目的 - O（1）查找 - 完全被破坏了。这在以下时间测量中得到了证明（使用 IPython 进行）。

一些时间测量

>>> 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键，因为元组是不可变且可哈希的。