列表不可哈希，但元组可哈希？

Question

在 如何对列表进行哈希处理？ 中，我被告知应该首先将其转换为元组，例如将 [1,2,3,4,5] 转换为 (1,2,3,4,5)。

因此，第一个无法被哈希，但第二个可以。为什么^*？

---

* _{我并不真正寻求详细的技术解释，而是想要一种直观的理解}

- gsamaras

Answer 1

主要是因为元组是不可变的。假设以下代码可以正常运行：

>>> l = [1, 2, 3]
>>> t = (1, 2, 3)
>>> x = {l: 'a list', t: 'a tuple'}

现在，当你执行l.append(4)时会发生什么？你已经远程修改了字典中的键！如果你熟悉哈希算法的工作原理，这应该让你感到恐惧。而元组则是绝对不可变的。t += (1,)看起来像是修改了元组，但实际上并没有：它只是创建了一个新的元组，保持你的字典键不变。

- val

---

Val，非常好的解释！您在这里想要表达什么？“从远处”？您认为这个问题很差以至于会被踩吗？ - gsamaras

我的意思是，您已经从字典之外修改了字典的键：由于哈希表依赖于键和哈希之间的1:1（ish）对应关系，因此在哈希背后修改键是一个非常糟糕的想法。 - val

您并没有说明修改键为什么是不好的——因为它会改变键的哈希值，这意味着存储键/值对的位置将变得无效，因此您将不能再检索到该键/值对。另外，哈希表可以使用∞:1键哈希对应（所有键具有相同的哈希值）。影响的只是它们的性能。 - Dunes

@Dunes，你能详细说明一下吗？ - gsamaras

Answer 2

你完全可以做到，但我敢打赌你不会喜欢它的效果。

from functools import reduce
from operator import xor

class List(list):
    def __hash__(self):
        return reduce(xor, self)

现在让我们看看会发生什么：

>>> l = List([23,42,99])
>>> hash(l)
94
>>> d = {l: "Hello"}
>>> d[l]
'Hello'
>>> l.append(7)
>>> d
{[23, 42, 99, 7]: 'Hello'}
>>> l
[23, 42, 99, 7]
>>> d[l]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: [23, 42, 99, 7]

---

编辑: 我再考虑了一下。如果您将列表的ID作为其哈希值返回，则可以使上述示例起作用：

class List(list):
    def __hash__(self):
        return id(self)

在这种情况下，d[l]将会给你'Hello'，但是d[[23,42,99,7]]和d[List([23,42,99,7])]都不会（因为你正在创建一个新的[Ll]ist）。

- L3viathan

Answer 3

由于列表是可变的，如果您对其进行修改，您将修改其哈希值，这破坏了拥有哈希值的意义（例如在集合或字典键中）。

编辑：我惊讶地发现这个答案经常获得新的赞，它是非常快速地编写的。我现在感觉需要把它做得更好。

因此，集和字典本地数据结构是使用哈希映射实现的。Python中的数据类型可能具有特殊方法__hash__()，其将用于哈希映射的构建和查找。

只有不可变数据类型（int、string、tuple等）具有此方法，并且哈希值基于数据而不是对象的标识符。您可以通过以下方式进行检查

>>> a = (0,1)
>>> b = (0,1)
>>> a is b
False # Different objects
>>> hash(a) == hash(b)
True # Same hash

如果我们按照这个逻辑，修改数据将会改变哈希值，但是这样做的意义何在呢？这反而败坏了集合、字典或其它哈希用法的本意。

有趣的事实：如果你尝试使用字符串或整数 -5 <= i <= 256 进行这个例子，a is b 返回 True 是由于微小的优化（至少在 CPython 中）。

- polku

---

你能提供更多关于你所说内容的法律引用和内容吗？ - Vicrobot

我想迟到总比不来得好吧，O'Reilly出版社的《高性能Python》一书中，有关于内置数据结构实现的描述。 - polku

Answer 4

因为列表是可变的，而元组不是。

- Daniel Roseman

Answer 5

答案很好。原因是可变性。如果我们可以在字典中使用列表作为键（或任何可变对象），那么我们就可以通过改变该键来改变键，从而导致字典中该键的哈希值发生变化，因此我们将无法通过该键从该数据结构中检索到值。哈希值和哈希表用于通过将它们映射到存储实际值条目的索引来轻松地映射大量数据。

在此处阅读更多信息：

哈希表 & 哈希函数 & 关联数组

- Vicrobot

Answer 6

并非所有的元组都是可哈希的。例如，元组中包含列表作为一个元素。

x = (1,[2,3])
print(type(x))
print(hash(x))

- user1436465

---

正确，所以你需要将那些嵌套的列表转换成元组。 - Keith