可哈希，不可更改

Question

从最近的一个SO问题（请参阅在python中创建由列表建立索引的字典）中，我意识到我可能对python中可哈希和不可变对象的含义有错误的理解。在实践中，hashable是什么意思？可哈希和不可修改之间有什么关系？是否存在可哈希的可变对象或不可哈希的不可变对象？

Answer 1

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

不变性是一个想法，即对象创建后将不会以某种重要方式更改，尤其是可能以任何方式更改该对象的哈希值的方式。

这两个想法是相关的，因为用作哈希键的对象通常必须是不可变的，因此它们的哈希值不会改变。如果允许更改，则该对象在诸如哈希表之类的数据结构中的位置将发生变化，从而破坏了哈希效率的整个目的。

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

Answer 2

是否存在可哈希的可变对象或不可哈希的不可变对象？

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

>>> tt = (1, 2, (30, 40))

>>> hash(tt)

8027212646858338501

>>> tl = (1, 2, [30, 40])

>>> hash(tl)

TypeError: unhashable type: 'list'

哈希类型

原子不可变类型都是可哈希的，例如str，字节，数字类型

冻结集始终是可哈希的（根据定义，其元素必须可哈希）

元组仅在其所有元素都可哈希的情况下才可哈希

默认情况下，用户定义类型是可哈希的，因为它们的哈希值是其id（）

Answer 3

从Python词汇表：

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

散列性使对象可用作字典键和set成员，因为这些数据结构在内部使用散列值。

Python的所有不可变内置对象都是可哈希的，而没有可变容器（例如列表或字典）是可哈希的。作为用户定义类实例的对象默认情况下可哈希化；它们都比较不相等，并且其哈希值是其id（）。

字典和集合必须使用散列以在散列表中进行有效查找；散列值必须是不可变的，因为更改散列会弄乱数据结构并导致dict或set失败。使哈希值不可变的最简单方法是使整个对象不可变，这就是为什么经常将两者一起提到的原因。

尽管内置的可变对象都不是可哈希的，但可以使用不可变的哈希值来创建可变对象。通常仅对象的一部分代表其身份，而对象的其余部分包含可以自由更改的属性。只要哈希值和比较函数基于身份而不是可变属性，并且身份永不更改，就可以满足要求。