可哈希，不可变

Question

从最近的一个SO问题（参见Create a dictionary in python which is indexed by lists）中，我意识到我可能对python中hashable和immutable对象的含义有一个错误的概念。

• hashable在实践中是什么意思？
• hashable和immutable之间的关系是什么？
• 是否存在可哈希的可变对象或不可哈希的可变对象？

Answer 1

Hashing是以可重复的方式将一些大量数据转换成更小数量（通常是单个整数）的过程，以便可以在恒定时间（O(1)）的表中查找它，这对于高性能算法和数据结构很重要。

Immutability是这样一种想法，即对象在创建后不会以某种重要方式发生更改，特别是以任何可能更改该对象哈希值的方式。

这两种想法是相关的，因为用作散列键的对象通常必须是不可变的，这样它们的散列值就不会改变。如果允许它进行更改，则该对象在数据结构（如哈希表）中的位置将发生更改，然后哈希效率的整个目的将被破坏。

要真正理解这个想法，你应该尝试用C/C++语言来实现你自己的哈希表，或者读取^ {< CD2>}类的java实现。

Answer 2

• Are there mutable objects that are hashable or immutable objects that are not hashable?

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

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

哈希类型

• 原子不可变类型都是散列的，例如str、bytes、numeric类型
• 冻结的集合始终是可哈希的（其元素必须根据定义是可哈希的）
• 只有元组的所有元素都是哈希的，元组才是哈希的
• 默认情况下，用户定义的类型是散列的，因为它们的散列值是它们的id（）

Answer 3

从技术上讲，hashable意味着类定义__hash__()。根据文件：

__hash__() should return an integer. The only required property is that objects which compare equal have the same hash value; it is advised to somehow mix together (e.g. using exclusive or) the hash values for the components of the object that also play a part in comparison of objects.

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

虽然定义了__hash__()的可变对象是困难的，但也不是不可能的。