Hashable，不可变的

Question

从最近的一个SO问题（参见在Python中创建由列表索引的字典），我意识到我可能对Python中"可哈希（hashable）"和"不可变（immutable）"对象的含义有误解。

• 实践中“可哈希”是什么意思？
• “可哈希”与“不可变”的关系是什么？
• 是否存在既是可变对象又是可哈希的对象，或者不可哈希的不可变对象？

- joaquin

Answer 1

哈希是将大量数据以可重复的方式转换为一个较小的数据（通常是单个整数），以便在恒定时间内 (O(1)) 在表中查找，这对于高性能算法和数据结构非常重要。

不可变性指对象在创建后不会以某种重要方式发生变化，尤其是不会改变该对象的哈希值。

这两个概念相关，因为用作哈希键的对象必须通常是不可变的，以免它们的哈希值发生变化。 如果允许更改，则哈希表等数据结构中该对象的位置将发生变化，那么哈希的效率就被破坏了。

要真正理解这个想法，您应该尝试在C/C++等语言中实现自己的哈希表，或者阅读HashMap类的Java实现。

- maerics

---

另外，哈希表无法以任何高效的方式检测到其键的哈希值发生变化。这是一个常见的陷阱，例如在Java中，如果您修改用作键的对象，则HashMap将出现故障：既不能找到旧键也不能找到新键，即使您打印地图，也可以在地图上看到键。 - user319799

Hashable和Immutable有一定的关联但并不相同。例如，从继承“object”的自定义类创建的实例是可哈希的但不是不可变的。这些实例可以用作字典的键，但如果传递它们，则仍然可以修改它们。 - Pranjal Mittal

Answer 2

• 可变对象是否存在哈希化的情况？不可变对象是否有不可哈希化的情况？

在Python中，元组是不可变的，但仅当它的所有元素都是可哈希的时才可以哈希。

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'

可哈希类型

• 原子不可变类型都是可哈希的，例如 str、bytes、数字类型等
• 一个冻结集合总是可哈希的（根据定义，它的元素必须是可哈希的）
• 如果一个元组中所有元素都是可哈希的，则该元组是可哈希的
• 用户自定义类型默认情况下是可哈希的，因为它们的哈希值是它们的 id()

- Yihe

---

可变对象的哈希值：类对象。不可哈希的不可变对象：包含不可哈希元素的元组，如列表、字典或集合。在元素级别上，集合成员和字典键必须是可哈希/不可变的。 - Leon Chang

Answer 3

来自Python词汇表：

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

哈希性使对象可用作字典键和集合成员，因为这些数据结构在内部使用哈希值。

所有Python内置的不可变对象都是可哈希的，而没有可变容器（例如列表或字典）是可哈希的。用户定义类的实例默认情况下是可哈希的;它们都不相等，它们的哈希值是它们的id()。

在哈希表中进行高效查找，字典和集合必须使用哈希；哈希值必须是不可变的，因为更改哈希值将破坏数据结构并导致字典或集合失败。使哈希值不可变的最简单方法是使整个对象不可变，这就是为什么两者经常同时提到的原因。

虽然没有任何内置的可变对象是可哈希的，但是可以创建一个可变对象，其哈希值是不可变的。通常只有对象的一部分表示其标识，而对象的其余部分包含可以自由更改的属性。只要哈希值和比较函数基于标识而不是可变属性，并且标识从不更改，就满足要求。

- Mark Ransom

---

@Andrey: frozensets是可哈希的，而sets则不行；两者都只能包含可哈希的项。在Mark提到sets的地方，他是正确的，因此我认为他并不是指frozensets。 - tzot

默认情况下，用户定义的类定义了可哈希类型（哈希值就是对象的 id）。这在对象的生命周期内不会改变，因此它是可哈希的，但这并不意味着您不能定义可变类型！抱歉，但哈希性并不意味着不可变性。 - Scott Griffiths

@ScottGriffiths 我不知道为什么要花费我6年的时间才看到你的评论，但迟到总比没到好。我不知道我怎么会这么偏离轨道，因为我曾经哀叹过无法将可变对象放入C++ set中。我希望我的编辑可以修复问题。 - Mark Ransom

注意：Python词汇表已更新。并非所有内置对象都是可哈希的。如果不可变容器（如元组和冻结集合）的元素是可哈希的，则它们才是可哈希的。 - ThatNewGuy

Answer 4

技术上，可哈希意味着该类定义了__hash__()。根据文档：

__hash__()应返回一个整数。唯一必需的属性是比较相等的对象具有相同的哈希值；建议以某种方式混合（例如使用异或）对象的组成部分的哈希值，这些部分也参与对象的比较。

我认为对于Python内置类型，所有可哈希类型也都是不可变的。

可能很难但并非不可能拥有一个可变对象，它仍然定义了__hash__()。

- Andrew Jaffe

---

值得注意的是，默认情况下，__hash__ 被定义为返回对象的 id；您必须费些周折才能设置 __hash__ = None 使其不可哈希。此外，正如 Mark Ransom 所提到的，还有一个额外的条件，即仅当哈希值永远不会改变时，它才是可哈希的！ - Scott Griffiths

我认为这个答案有点误导性，“list”在某种意义上定义了“__hash__”，因为“hasattr([1,2,3]，'hash')”返回“True”，但是调用“hash([1,2,3])”会引发一个“TypeError”（Python 3），因此它并不是完全可哈希的。仅仅依赖于“__hash__”的存在是不足以确定一个对象既是a)可哈希的 b)不可变的。 - Matti Lyra

Answer 5

即使没有显式强制不可变和可哈希之间的关系，由于以下两个因素的相互作用，它们之间仍然存在隐含关系：

1. 具有相等比较的可哈希对象必须具有相同的哈希值
2. 如果一个对象在其生命周期中具有永远不会更改的哈希值，则该对象是可哈希的。

除非您重新定义了__eq__，否则这里没有问题，因此对象的类定义了基于值的等价性。

一旦您这样做了，您需要找到一个稳定的哈希函数，该函数始终为表示相同值的对象返回相同的值（例如，其中__eq__返回True），并且在对象的生命周期内永远不会更改。

很难看出这种情况可能出现的应用程序，考虑一个可能满足这些要求的类A。尽管存在__hash__返回常量的明显退化情况。

现在：

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

实际上，这意味着在创建时 hash(b) == hash(c)，尽管它们永远不会被比较相等。我很难想象如何有用地为通过值进行比较的可变对象定义__hash__()。

注意: __lt__，__le__，__gt__和__ge__比较没有受到影响，因此您仍然可以基于它们的值定义可哈希对象(不管它们是可变的还是不可变的)的排序。

- rgammans

Answer 6

Immutable指的是对象在其生命周期内不会发生任何重大变化。这是编程语言中一个模糊但常见的概念。

Hashable略有不同，它指的是比较。

可哈希如果一个对象具有哈希值（需要一个__hash __()方法），并且可以与其他对象进行比较（需要一个__eq__()或__cmp__()方法），则该对象是可哈希的，其哈希值在其生命周期内永远不会改变。比较相等的可哈希对象必须具有相同的哈希值。

所有用户定义的类都有__hash__方法，默认情况下只返回对象ID。因此，符合哈希性标准的对象不一定是不可变的。

您声明的任何新类的对象都可以用作字典键，除非您通过例如从__hash__抛出来防止它。

我们可以说所有不可变对象都是可哈希的，因为如果哈希值在对象生命周期中发生变化，那么这意味着对象已经发生了变异。

但并非完全如此。考虑一个包含列表（可变）的元组。有人说元组是不可变的，但同时它又有点不可哈希（会抛出异常）。

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

可哈希性和不可变性是指对象实例，而非类型。例如，元组类型的对象可以是可哈希的或不可哈希的。

- user2622016

---

可哈希对象比较相等时必须具有相同的哈希值。为什么？我可以创建比较相等但没有相同哈希值的对象。 - endolith

可以创建这样的对象，但这将违反Python文档中定义的概念。实际上，我们可以利用这个要求来推导出这样的（逻辑等价）蕴含：如果哈希值不相等，则对象不相等。非常有用。许多实现、容器和算法都依赖于这个蕴含来加速处理。 - user2622016

常见情况下，comparison != identity 的情况是当比较“无效”的值时，例如 float("nan") == float("nan")，或者来自切片的内部字符串："apple" is "apple" 与 "apple" is "crabapple"[4:]。 - sleblanc

Answer 7

仅因为这是谷歌的热门搜索结果，这里提供一种简单的方法来使可变对象具有哈希值：

>>> class HashableList(list):
...  instancenumber = 0  # class variable
...  def __init__(self, initial = []):
...   super(HashableList, self).__init__(initial)
...   self.hashvalue = HashableList.instancenumber
...   HashableList.instancenumber += 1
...  def __hash__(self):
...   return self.hashvalue
... 
>>> l = [1,2,3]
>>> m = HashableList(l)
>>> n = HashableList([1,2,3])
>>> m == n
True
>>> a={m:1, n:2}
>>> a[l] = 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> m.hashvalue, n.hashvalue
(0, 1)

实际上，我在创建一个类时发现这样的用途，该类将SQLAlchemy记录转换为可变且对我更有用的东西，同时保持其可哈希性以便用作字典键。

- jcomeau_ictx

Answer 8

在Python中，它们大多是可以互换的；因为哈希应该代表内容，所以它与对象一样可变，如果一个对象改变了哈希值，那么它就不能用作字典键。

在其他语言中，哈希值更多地与对象的“身份”相关，而不是（必然）与值相关。因此，对于可变对象，指针可以用于开始哈希。当然，假设对象不会在内存中移动（某些GC会这样做）。例如，Lua使用的就是这种方法。这使得可变对象可用作表键；但对于新手来说，这会产生几个（不愉快的）惊喜。

最终，拥有一个不可变序列类型（元组）使得“多值键”更加美好。

- Javier

---

在Python中，它们大多是可以互换的。我的疑问是指“mostly”未包含的小部分。 - joaquin

Answer 9

可哈希意味着变量的值可以被表示（或编码）为常量 - 字符串、数字等。现在，任何可变的东西都是易变的，不能用不变的东西来表示。因此，任何可变的变量都不能是可哈希的，同样地，只有不可变的变量才能是可哈希的。

希望这可以帮助到您...

- ktdrv