python - 为什么要使列表不可散列？

Question

SO 上的一个常见问题是 removing duplicates from a list of lists .由于列表是不可散列的，set([[1, 2], [3, 4], [1, 2]]) 抛出 TypeError: unhashable type: 'list' .这类问题的答案通常涉及使用元组，它们是不可变的，因此是可散列的。

这个对 What makes lists unhashable? 的回答包括以下内容:

If the hash value changes after it gets stored at a particular slot in the dictionary, it will lead to an inconsistent dictionary. For example, initially the list would have gotten stored at location A, which was determined based on the hash value. If the hash value changes, and if we look for the list we might not find it at location A, or as per the new hash value, we might find some other object.

但我不太明白，因为可以毫无问题地更改可用于字典键的其他类型:

>>> d = {}
>>> a = 1234
>>> d[a] = 'foo'
>>> a += 1
>>> d[a] = 'bar'
>>> d
{1234: 'foo', 1235: 'bar'}

很明显，如果a的值发生变化，它会散列到字典中的不同位置。 为什么相同的假设对列表来说是危险的？为什么下面的散列列表方法是不安全的，因为无论如何我们都会在需要时使用它？

>>> class my_list(list):
...   def __hash__(self):
...     return tuple(self).__hash__()
...
>>> a = my_list([1, 2])
>>> b = my_list([3, 4])
>>> c = my_list([1, 2])
>>> foo = [a, b, c]
>>> foo
[[1, 2], [3, 4], [1, 2]]
>>> set(foo)
set([[1, 2], [3, 4]])

这似乎解决了 set() 问题，为什么这是一个问题？列表可能是可变的，但它们是有序的，这似乎是散列所需的全部内容。

Answer 1

您似乎混淆了可变性和重新绑定(bind)。 a += 1 将一个新对象，即数值为 1235 的 int 对象分配给 a。在底层，对于像 int 这样的不可变对象(immutable对象)，a += 1 与 a = a + 1 是一样的。

原始的 1234 对象没有发生变化。该字典仍然使用一个 int 对象，其数值为 1234 作为键。字典仍然保留对该对象的引用，即使a 现在引用了不同的对象。这两个引用是独立的。

试试这个:

>>> class BadKey:
...     def __init__(self, value):
...         self.value = value
...     def __eq__(self, other):
...         return other == self.value
...     def __hash__(self):
...         return hash(self.value)
...     def __repr__(self):
...         return 'BadKey({!r})'.format(self.value)
...
>>> badkey = BadKey('foo')
>>> d = {badkey: 42}
>>> badkey.value = 'bar'
>>> print(d)
{BadKey('bar'): 42}

请注意，我更改了 badkey 实例上的属性 value。我什至没有碰字典。字典反射(reflect)变化； 实际键值本身发生了变异，即名称 badkey 和字典引用的对象。

但是，您现在无法再访问该 key :

>>> badkey in d
False
>>> BadKey('bar') in d
False
>>> for key in d:
...     print(key, key in d)
...
BadKey('bar') False

我已经彻底破解了我的字典，因为我无法再可靠地找到 key 。

那是因为BadKey违反了hashability的原则；哈希值必须保持稳定。只有当您不更改散列所基于的对象的任何内容时，您才能这样做。并且哈希必须基于使两个实例相等的任何因素。

对于列表，内容 使两个列表对象相等。而且您可以更改它们，因此您也无法生成稳定的哈希值。