可洗,不变

Question

从最近的SO问题(参见在python中创建一个由列表索引的字典)我意识到我可能对python中可散列和不可变对象的含义有一个错误的概念.

• 在实践中,什么是可以平均的？
• hashable和immutable之间的关系是什么？
• 是否有可变对象是可清洗的或不可变的对象？

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,bytes,numeric类型
• 冻结集总是可以清除的(根据定义,其元素必须是可清除的)
• 元组只有在其所有元素都可以清洗时才可以清洗
• 用户定义的类型默认是可哈希的,因为它们的哈希值是它们的id()

Answer 3

从技术上讲,hashable意味着类定义__hash__().根据文件:

__hash__()应该返回一个整数.唯一需要的属性是比较相等的对象具有相同的哈希值; 建议以某种方式将对象的组件的哈希值混合在一起(例如,使用异或),这些哈希值也在对象的比较中起作用.

我认为对于Python内置类型,所有可清除类型也是不可变的.

拥有一个仍然定义的可变对象将是困难的,但也许并非不可能__hash__().

Answer 4

从Python词汇表:

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

Hashability使对象可用作字典键和set成员,因为这些数据结构在内部使用哈希值.

所有Python的不可变内置对象都是可清除的,而没有可变容器(例如列表或字典).默认情况下,作为用户定义类实例的对象是可清除的; 他们都比较不相等,他们的哈希值是他们的id().

Dicts和sets必须使用哈希来在哈希表中进行有效查找; 散列值必须是不可变的,因为更改散列会弄乱数据结构并导致dict或set失败.使哈希值不可变的最简单方法是使整个对象不可变,这就是为什么这两个经常被一起提到的原因.

虽然没有内置的可变对象是可以清除的,但是可以使用不可变的哈希值来创建一个可变对象.通常只有对象的一部分表示其标识,而对象的其余部分包含可自由更改的属性.只要哈希值和比较函数基于标识但不基于可变属性,并且标识永远不会更改,您就满足了要求.