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

Question

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

8

在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()的问题，但这为什么是个问题呢？列表可能是可变的，但它们是有序的，这似乎就足够用于哈希。

- Will

3

你没有修改存储的 key，而是将一个 新对象 分配给了 a。 - Martijn Pieters

3

它们完全不同。在第一种情况下，你只是使用了一个不同的对象：1235而不是1234。这不是被改变的同一对象，对于列表来说则不同。 - Daniel Roseman

可能是什么使列表不可哈希？的重复问题。 - Robert Columbia

1

如果 a += 1; print(d[a]) 的结果是 'foo'，那么你的数字示例就是正确的。但事实并非如此。然而，使用一个已变异的列表就可以实现这一点（如果可变列表可以用作键，但它们不能，因为这样做没有意义）。 - deceze

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martijn Pieters · Accepted Answer

你好像将可变性和重新绑定混淆了。a += 1将一个新对象，即数字值为1235的int对象赋给了a。对于像int这样的不可变对象，在幕后，a += 1与a = a + 1是一样的。

原始的1234对象未被改变。字典仍然使用数字值为1234的int对象作为键。尽管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。我甚至没有触及字典。字典反映了这种变化；实际键值本身被改变，即名称badkey和字典引用的对象被改变。

但是，您现在无法再访问该键：

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

我已经彻底弄坏了我的字典，因为我不能再可靠地定位键。

这是因为BadKey违反了哈希性原则；哈希值必须保持稳定。只有在不改变哈希基于的对象的任何内容的情况下才能实现此目标。而哈希必须基于使两个实例相等的任何内容。

对于列表来说，内容使得两个列表对象相等。而这些内容是可以改变的，因此也无法产生稳定的哈希值。