可哈希对象必须是不可变的

Reddit 最近的一篇帖子引发了一些评论，所以我想澄清一下：在 Python 中，可哈希对象必须是不可变的，可变对象不能是可哈希的。 （有一个例外。）

在收集火炬和干草叉之前，让我解释一下背景。

如果你想让你的类可散列，你必须遵循 Python 词汇表中关于“可散列”条目的两条规则：

一个对象是可哈希的，如果 [1] 它有一个哈希值，在其生命周期内永远不会改变（它需要一个 __hash__() 方法），并且可以与其他对象进行比较（它需要一个 __eq__() 方法）。 [2] 比较相等的可散列对象必须具有相同的散列值。

在 Python 中，整数、浮点数和布尔值都是不可变的。 而且因为 1 == 1.0 == True， 然后 hash(1) == hash(1.0) == hash(True).

让我们创建一个不可变的 Point 类，它具有只读的 x 和 y 属性，并重用元组的哈希值：

>>> class ImmutablePoint:
...   def __init__(self, x, y):
...     self._x = x
...     self._y = y
...   def __eq__(self, other):
...     if not isinstance(other, ImmutablePoint):
...       return False
...     return self._x == other._x and self._y == other._y
...   def __hash__(self):
...     return hash((self._x, self._y))
...   @property
...   def x(self):
...     return self._x
...   @property
...   def y(self):
...     return self._y

我们可以创造 ImmutablePoint 对象，它们是不可变的：我们不能改变它们 x 或者 y 属性：

>>> ip = ImmutablePoint(10, 20)

>>> ip.x, ip.y
(10, 20)

>>> ip.x = 'changed' # x and y are read-only
Traceback (most recent call last):
  File "stdin", line 1, in module
AttributeError: can't set attribute

>>> ip2 = ImmutablePoint(10, 20)

>>> ip == ip2
True

由于它们是可哈希的，我们还可以将这些对象用作字典中的键：

>>> d = {ip: 'hello'}

>>> d[ip]
'hello'

>>> d[ip2]
'hello'

现在，由于散列基于对象的值，并且对象的散列永远不会改变（根据 Python 词汇表的规则），这必然意味着只有不可变的对象才可以散列。 请注意，您不能将可变列表或字典用作字典中的键，它们也不会从 hash():

>>> {[1, 2, 3]: 'hello'}
Traceback (most recent call last):
  File "stdin", line 1, in module
TypeError: unhashable type: 'list'

>>> hash([1, 2, 3])
Traceback (most recent call last):
  File "stdin", line 1, in module
TypeError: unhashable type: 'list'

>>> hash({1:2, 3:4})
Traceback (most recent call last):
  File "stdin", line 1, in module
TypeError: unhashable type: 'dict'

但为什么会这样呢？ 使可变对象可哈希有什么不好？ 我们可以添加一个 __hash__() 我们可变类的方法，对吧？

原因与哈希在字典中的使用方式有关。 这将需要一些关于字典/哈希图如何工作的 CS 背景（但您可以观看 Brandon Rhode 的 PyCon 2010 演讲，The Mighty Dictionary）。 但简短的回答是，如果对象的值发生变化，那么哈希值也必须发生变化，因为哈希值是基于值的。 但是，如果对象的值在用作字典中的键后发生变化，则哈希将不再引用字典中该键的正确存储桶。 让我们举个例子。

这是我们添加的 Python 内置列表数据类型（可变的）的子类 __hash__() 作用于：

>>> import collections

>>> class HashableList(collections.UserList):
...     def __hash__(self):
...         return hash(tuple(self))

我们可以创建一个可哈希列表对象并将其放入字典中：

>>> h = HashableList([1, 2, 3])

>>> d = {h: 'hello'}

>>> d
{[1, 2, 3]: 'hello'}

它似乎工作。 我们甚至制作了另一个具有相同值的可哈希列表，它似乎也有效：

>>> d[h]
'hello'

>>> h2 = HashableList([1, 2, 3])

>>> d[h2]
'hello'

现在我们改变 h. 正如预期的那样，它创建了一个 KeyError 因为 [1, 2, 100] 不是字典中的键，只有 [1, 2, 3] 是（事实证明这是错误的，但暂时忽略它）：

>>> h[2] = 100

>>> d[h]
Traceback (most recent call last):
  File "stdin", line 1, in module
KeyError: [1, 2, 100]

但事情是这样的。 h2 不再作为钥匙使用，即使它是 [1, 2, 3]:

>>> d[h2]
Traceback (most recent call last):
  File "stdin", line 1, in module
KeyError: [1, 2, 3]

为什么是这样？ 因为关键在 d 不是的副本 [1, 2, 3] 对象，它是引用的副本。 当我们改变 h，我们还更改了字典键：

>>> d
{[1, 2, 100]: 'hello'}

所以这意味着关键是现在 [1, 2, 100]，但它在桶/插槽中 [1, 2, 3]. 但 h2的 [1, 2, 3] 不会工作，因为键的值现在是 [1, 2, 100] 而 Python 只是假设它恰好是哈希冲突。

更糟糕的是，尝试设置 h[2] 到 99. 纯属巧合， [1, 2, 99] 散列到与相同的桶/槽 [1, 2, 3]. 并且值是相同的（因为密钥也已更改为 [1, 2, 99]) 所以它工作得很好，即使它会导致 KeyError:

>>> h[2] = 99 # You might need to find another integer to reproduce this, depending on your Python version.

>>> d[h]
'hello'

所以这就是为什么让可变项目可哈希是一件坏事：改变它们也会改变字典中的键。 有时这会起作用，即使它会导致 KeyError （当碰巧发生哈希冲突时）和其他时候它会导致 KeyError 它应该在什么时候工作（因为当可变对象改变时字典键也改变了）。

但是等等，唯一的例外是什么？ 好吧，一个可变对象可以是可散列的并用作字典键，只要它的散列和值与其标识（或其他一些唯一的、不变的整数）相同。 也就是说，它必须具有以下内容 __eq__() 和 __hash__() 实施：

>>> class SomeClass:
...   def __eq__(self, other):
...     return other is self
...   def __hash__(self):
...     return id(self)

这也恰好是 Python 类的默认实现，因此我们可以将我们的类缩短为以下内容：

>>> class SomeClass:
...   pass

在这种情况下，我们支持可哈希性的两个规则。 但是我们并没有真正有用的类，因为类型的每个对象 SomeClass 只等于它自己，并且永远是 False 与任何其他对象相比时，无论它的价值是多少。

>>> sc = SomeClass()

>>> {sc: 'hello'}
{: 'hello'}

>>> sc2 = SomeClass()

>>> sc == sc2
False

因此，您可以为您的类遵循 Python 的两个可哈希性规则，或者您可以创建实际上在字典中不起作用的可变、可哈希对象。 当您可以拥有一个可变的、可散列的类时，唯一的例外是散列基于标识而不是值，这严重限制了它作为字典键的用途。 这意味着，实际上，只有不可变对象可以被散列，而可变对象不能被散列。

鳍。

阅读更多