为什么以及如何Python函数可散列?

我最近在Python中尝试了以下命令:

>>> {lambda x: 1: 'a'} {<function __main__.<lambda>>: 'a'} >>> def p(x): return 1 >>> {p: 'a'} {<function __main__.p>: 'a'} 

这两个dict创作的成功表明,lambda函数和常规函数都是可散列的。 (类似于{[]: 'a'} TypeError: unhashable type: 'list' )失败。

散列显然不一定是函数的ID:

 >>> m = lambda x: 1 >>> id(m) 140643045241584 >>> hash(m) 8790190327599 >>> m.__hash__() 8790190327599 

最后一个命令显示__hash__方法是为lambda明确定义的,也就是说,这不是Python根据types计算的一些自动操作的东西。

背后的动机是什么? 对于奖金,函数的散列是什么?

没什么特别的 正如你可以看到,如果你检查函数types的未绑定__hash__方法:

 >>> def f(): pass ... >>> type(f).__hash__ <slot wrapper '__hash__' of 'object' objects> 

of 'object' objects部分意味着它只是从objectinheritance默认的基于身份的__hash__ 。 函数==hash工作的身份。 对于任何inheritanceobject.__hash__types, idhash之间的区别是正常的object.__hash__

 >>> x = object() >>> id(x) 40145072L >>> hash(x) 2509067 

你可能会认为__hash__只能被定义为不可变的对象,而且你几乎是正确的,但是缺less一个关键的细节。 __hash__只应该定义为==比较涉及的所有内容都是不可变的对象。 对于基于身份的==对象,基于身份的hash也是完全标准的,因为即使对象是可变的,它们也不可能以改变其身份的方式变化。 文件,模块和其他基于身份的可变对象==都是这样的。

例如,创build函数对象集合或者通过函数索引字典是很有用的。 不可变对象通常支持__hash__ 。 在任何情况下,由deflambda定义的函数之间没有内在的区别 – 纯粹是句法。

使用的algorithm取决于Python的版本。 它看起来像你在64位盒子上使用Python的最新版本。 在这种情况下,函数对象的哈希是它的id()右移4位,结果被看作是一个有符号的64位整数。 因为对象地址( id()结果)通常是alignment的,所以它们的最后3或4位总是0,这对于散列函数来说是一个轻度恼人的属性。

在你的具体例子中,

 >>> i = 140643045241584 # your id() result >>> (i >> 4) | ((i << 60) & 0xffffffffffffffff) # rotate right 4 bits 8790190327599 # == your hash() result 

一个函数是可散的,因为它是一个正常的,内置的,不可变的对象。

从Python手册 :

如果一个对象具有在其生命周期中从不改变的散列值(它需要__hash__()方法),并且可以与其他对象进行比较(它需要__eq__()__cmp__()方法),则该对象是可散列的。 比较相等的哈希对象必须具有相同的哈希值。

Hashability使对象可用作字典键和集合成员,因为这些数据结构在内部使用散列值。

所有Python的不可变内置对象都是可散列的,而没有可变容器(如列表或字典)。 对象是用户定义的类的实例默认可哈希; 他们都比较不平等(除了自己),他们的哈希值是从他们的id()派生。