列表不可用,但元组可以清除？

Question

在如何哈希列表？有人告诉我,我应该转换为一个元组第一,如[1,2,3,4,5]到(1,2,3,4,5).

所以第一个不能被哈希,但第二个可以.为什么^*？

---

*_{我并不是在寻找详细的技术解释,而是为了直觉}

Answer 1

主要是因为元组是不可变的.假设以下工作:

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

现在,当你这样做时会发生什么l.append(4)？你修改了字典中的密钥!远道而来!如果你熟悉散列算法是如何工作的,这应该会吓到你.另一方面,元组绝对是不可变的.t += (1,)可能看起来它正在修改元组,但实际上它不是:它只是创建一个新的元组,保持字典键不变.

Answer 2

由于列表是可变的，如果你修改它，你也会修改它的散列，这破坏了拥有散列的意义（如在集合或字典键中）。

编辑：我很惊讶这个答案经常得到新的支持，它写得真的很快。我觉得我现在需要让它变得更好。

所以 set 和 dict 原生数据结构是用 hashmap 实现的。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由于微优化（至少在 CPython 中），返回 True。

Answer 3

你可以完全做到这一点,但我打赌你不会喜欢这些效果.

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.

Answer 4

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