可哈希的，不可变的
在最近的一个StackOverflow问题中（见在Python中创建一个以列表为索引的字典），我意识到我可能对Python中“可哈希”和“不可变”对象的含义有些误解。
- 可哈希在实际中是什么意思？
- 可哈希和不可变之间有什么关系？
- 有没有可变对象是可哈希的，或者不可变对象是不可哈希的？
9 个回答
来自Python 词汇表的内容：
一个对象是“可哈希”的，意思是它有一个在整个生命周期内不会改变的哈希值（这需要一个
__hash__()方法），并且可以和其他对象进行比较（这需要一个__eq__()或__cmp__()方法）。如果两个可哈希的对象比较后是相等的，它们的哈希值也必须相同。可哈希性使得一个对象可以用作字典的键和集合的成员，因为这些数据结构在内部使用哈希值。
所有Python内置的不可变对象都是可哈希的，而没有可变容器（比如列表或字典）是可哈希的。用户自定义类的实例默认是可哈希的；它们之间比较都是不相等的，哈希值就是它们的id()。
字典和集合必须使用哈希值来高效查找，因为它们使用哈希表；哈希值必须是不可变的，因为如果哈希值改变了，会搞乱数据结构，导致字典或集合无法正常工作。让哈希值不可变的最简单方法就是让整个对象不可变，这也是为什么这两者常常一起提到。
虽然内置的可变对象都不可哈希，但可以创建一个可变对象，其哈希值是不可变的。通常情况下，只有对象的一部分代表它的身份，而其他部分的属性是可以改变的。只要哈希值和比较函数是基于身份而不是可变属性，并且身份永远不变，你就满足了要求。
- 有没有可变对象是可哈希的，或者不可变对象是不可哈希的呢？
在Python中，元组是不可变的，但只有当它的所有元素都是可哈希的时候，它才是可哈希的。
>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'
可哈希的类型
- 所有原子不可变类型都是可哈希的，比如字符串（str）、字节（bytes）、数字类型。
- 一个冻结集合（frozen set）总是可哈希的（因为它的元素必须是可哈希的）。
- 元组只有在它的所有元素都是可哈希的情况下才是可哈希的。
- 用户自定义的类型默认是可哈希的，因为它们的哈希值就是它们的id()。
哈希是一种把大量数据转换成更小的数据（通常是一个整数）的过程，这个过程是可以重复的。这样做的好处是可以在一个表里快速查找数据，时间复杂度是常量级别的（O(1)），这对于高效的算法和数据结构来说非常重要。
不可变性的意思是一个对象在创建后不会以某种重要的方式发生变化，特别是不会改变这个对象的哈希值。
这两个概念是相关的，因为作为哈希键的对象通常需要是不可变的，这样它们的哈希值才不会改变。如果允许对象改变，那么在像哈希表这样的数据结构中，这个对象的位置也会改变，那样的话，使用哈希来提高效率的目的就失去了意义。
要真正理解这个概念，你可以尝试用C/C++语言自己实现一个哈希表，或者阅读Java中HashMap类的实现。