为什么列表不可用？

Question

SO上的一个常见问题是从列表列表中删除重复项.由于列表不可用,因此set([[1, 2], [3, 4], [1, 2]])抛出TypeError: unhashable type: 'list'.这类问题的答案通常涉及使用元组,元组是不可变的,因此可以清除.

这个回答什么使得列表不可用？包括以下这些:

如果散列值在存储在字典中的特定插槽后发生更改,则会导致字典不一致.例如,最初列表将存储在位置A,该位置是基于散列值确定的.如果哈希值发生变化,如果我们查找列表,我们可能无法在位置A找到它,或者根据新的哈希值,我们可能会找到一些其他对象.

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

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

你似乎把可变性与重新绑定混为一谈.a += 1分配一个新对象,即int数值为1235 的对象a.在引擎盖下,对于不可变的对象int,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}

请注意,我更改value了badkey实例上的属性.我甚至都没碰过字典.字典反映了这种变化; 在实际的密钥值本身突变,对象,无论是名字badkey和字典参考.

但是,您现在无法再访问该密钥:

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

我彻底破坏了我的字典,因为我无法再可靠地找到密钥了.

那是因为BadKey违反了可持续性的原则; 哈希值必须保持稳定.如果您不更改有关散列所基于的对象的任何内容,则只能执行此操作.并且散列必须基于使两个实例相等的任何东西.

对于列表,内容使两个列表对象相等.你可以改变那些,所以你也不能产生稳定的哈希.