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

Question

我想有一个列表,它是字典中的一个键,定义如下:

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))])

Answer 1

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

\n\n

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

\n\n

实施例1：对可变对象进行哈希处理，其中哈希值基于对象的可变特征。

\n\n

>>> class stupidlist(list):\n...     def __hash__(self):\n...         return len(self)\n... \n>>> stupid = stupidlist([1, 2, 3])\n>>> d = {stupid: 0}\n>>> stupid.append(4)\n>>> stupid\n[1, 2, 3, 4]\n>>> d\n{[1, 2, 3, 4]: 0}\n>>> stupid in d\nFalse\n>>> stupid in d.keys()\nFalse\n>>> stupid in list(d.keys())\nTrue\n

\n\n

mutating 后stupid，由于哈希值发生了变化，因此无法再在字典中找到它。仅对字典键列表进行线性扫描才能找到stupid。

\n\n

实施例2：...但为什么不只是一个常量哈希值呢？

\n\n

>>> class stupidlist2(list):\n...     def __hash__(self):\n...         return id(self)\n... \n>>> stupidA = stupidlist2([1, 2, 3])\n>>> stupidB = stupidlist2([1, 2, 3])\n>>> \n>>> stupidA == stupidB\nTrue\n>>> stupidA in {stupidB: 0}\nFalse\n

\n\n

这也不是一个好主意，因为相等的对象应该进行相同的散列，这样您就可以在 adict或中找到它们set中找到它们。

\n\n

实施例3：...好吧，那么所有实例的常量哈希怎么样？！

\n\n

>>> class stupidlist3(list):\n...     def __hash__(self):\n...         return 1\n... \n>>> stupidC = stupidlist3([1, 2, 3])\n>>> stupidD = stupidlist3([1, 2, 3])\n>>> stupidE = stupidlist3([1, 2, 3, 4])\n>>> \n>>> stupidC in {stupidD: 0}\nTrue\n>>> stupidC in {stupidE: 0}\nFalse\n>>> d = {stupidC: 0}\n>>> stupidC.append(5)\n>>> stupidC in d\nTrue\n

\n\n

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

\n\n

找到正确的实例 withd[key]或key in d需要执行与 的实例一样多的相等性检查stupidlist3需要执行与字典键中的此时，字典的目的——O(1)查找——就完全落空了。以下时间演示了这一点（使用 IPython 完成）。

\n\n

一些时间安排

\n\n

>>> lists_list = [[i]  for i in range(1000)]\n>>> stupidlists_set = {stupidlist3([i]) for i in range(1000)}\n>>> tuples_set = {(i,) for i in range(1000)}\n>>> l = [999]\n>>> s = stupidlist3([999])\n>>> t = (999,)\n>>> \n>>> %timeit l in lists_list\n25.5 \xc2\xb5s \xc2\xb1 442 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 10000 loops each)\n>>> %timeit s in stupidlists_set\n38.5 \xc2\xb5s \xc2\xb1 61.2 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 10000 loops each)\n>>> %timeit t in tuples_set\n77.6 ns \xc2\xb1 1.5 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 10000000 loops each)\n

\n\n

正如您所看到的，我们的成员资格测试stupidlists_set甚至比整个 的线性扫描还要慢lists_list，而您在一组中具有预期的超快查找时间（因子 500），而没有哈希冲突负载。

\n\n\n\n

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

\n

Answer 2

您可以使用元组作为字典键:

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

print data[(24,48,96)]