python - 为什么列表不能用作字典键？

Question

<分区>

Answer 1

我正在回答这篇文章标题中的问题。 :)

因为列表是可变的，dict 键需要是可散列的，散列可变对象是一个坏主意，因为散列值应该根据实例属性计算。

示例 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 中。

使用 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 的线性扫描还要慢，而您拥有预期的超快查找时间 ( factor 500) 在一个没有大量散列冲突的集合中。

---

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