《Python面向对象编程指南》——2.3　__hash__()方法

2.3　__hash__()方法

内置的hash( )函数默认调用了__hash__()方法。哈希是一种将相对复杂的值简化为小整数的计算方式。理论上说，一个哈希值可以表示出源值的所有位。还有一些其他的哈希方法，会得出非常大的值，这样的算法通常用于密码学。

Python中有两个哈希库。其中，hashlib可以提供密码级别的哈希函数，zlib模块包含两个高效的哈希函数：adler32()和crc32()。对于相对简单的值，我们不使用这些内置的函数，对于复杂的或者很大的值，这些内置的函数可以提供很大的帮助。

hash()函数（以及与其相关联的__hash__()方法）主要被用来创建set、frozenset和dict这些集合类型的键。这些集合利用不可变对象的哈希值来高效地查找集合中的对象。

在这里，不可变性是非常重要的，我们还会多次提到它。不可变对象不会改变自己的状态。例如，数字3不会改变状态，它永远是3。对于更复杂的对象，同样可以有一个不变的状态。Python中的string是不可变的，所以它们可以被用作map和set的键。

object中默认的__hash__()方法的实现是基于对象内部的ID值生成哈希值。这个ID值可以用id()函数查看：

>>> x = object()
>>>hash(x)
269741571
>>>id(x)
4315865136
>>>id(x) / 16
269741571.0

可以看到，在笔者的系统中，哈希值是用对象的id除以16算出来的。对于不同的平台，哈希值的计算方法有可能不同。例如，CPython使用portable c库，而Jython则基于JVM。

这里最关键的是，在__hash__()和内部的ID之间有很强的依赖关系。__hash__()方法默认的行为是要保证每一个对象都是可哈希的，并且哈希值是唯一的，即使这些对象包含同样的值。

如果我们希望包含同样值的不同对象有相同的哈希值，就需要修改这个方法。在下一节中，我们会展示一个例子，这个例子中，具有相同值的两个Card实例被当作相同的对象。

2.3.1　决定哈希的对象

并非每个对象都需要提供一个哈希值，尤其是，当我们创建一个包含有状态、可改变对象的类时，这个类不应该返回哈希值。__hash__的定义应该是None。

另外，对于不可变的对象，可以显式地返回一个哈希值，这样这个对象就可以用作字典中的一个键或者集合中的一个成员。在这种情况下，哈希值需要和相等性判断的实现方式兼容。相同的对象返回不同的哈希值是很糟糕的实践。反之，具有相同哈希值的对象互相不等是可以接受的。

我们将在比较运算符一章中讲解的__eq__()方法也和哈希有紧密的关联。

等价性比较有3个层次。

• 哈希值相等：这意味两个对象可能相等。哈希值是判断两个对象有可能相等的快捷方式。如果哈希值不同，两个对象不可能相等，也不可能是同一个对象。
• 比较结果相等：这意味着两个对象的哈希值已经是相等的，这个比较用的是==运算符。如果结果相等，那么两个对象有可能是同一个。
• IDD相等：这意味着两个对象是同一个对象。它们的哈希值相同，并且使用==的比较结果相等，这个比较用的是is运算符。

基本哈希法（Fundamental Law of Hash，FLH）定义如下：比较相等的对象的哈希值一定相同。

我们可以认为哈希比较是等价性比较的第1步。

反之则不成立，有相同哈希值的对象不一定相等。当创建集合或字典时，这带来了==预期的处理开销。我们没有办法从更大的数据结构中可靠地创建64位不同的哈希值，这时就会出现不同的对象的哈希值碰巧相等的情况。

巧合的是，当使用sets和dicts的时候，计算哈希值相等是预期的开销。这些集合中有一些内置的算法，当哈希值出现冲突的时候，它们会使用备用的位置。

对于以下3种情况，需要使用__eq__()和__hash__()方法来定义相等性测试和哈希值。

• 不可变对象：这些是不可以修改的无状态类型对象，例如tuple、namedtuple和frozenset。我们针对这种情况有两个选择。

• 不用自定义__hash__()和__eq__()。这意味着直接使用继承而来的行为。这种情况下，__hash__()返回一个简单的函数代表对象的ID值，然后__eq__()比较对象的ID值。默认相等性测试的行为有时候比较反常。我们的应用程序可能会需要Card(1, Clubs)的两个实例来测试相等性和计算哈希值，但是默认情况下这不会发生。
• 自定义__hash__()和__eq__()。请注意，这种自定义必须是针对不可变对象。
• 可变对象：这些都是有状态的对象，它们允许从内部修改。设计时，我们有一个选择如下。
• 自定义__eq__()，但是设置__hash__为None。这些对象不可以用作dict的键和set中的项目。

除了上面的选择之外，还有一种可能的组合：自定义__hash__()但使用默认的__eq__()。但是，这简直是浪费代码，因为默认的__eq__()方法和is操作符是等价的。对于相同的行为，使用默认的__hash__()方法只需要写更少的代码。

接下来，我们细致地分析一下以上3种选择。

2.3.2　有关不可变对象和继承的默认行为

首先，我们来看看默认行为是如何工作的。下面是一个使用了默认__hash__()和__eq__()的简单类。

class Card:
 　　insure= False
 　　def __init__( self, rank, suit, hard, soft ):
 　　　　self.rank= rank
 　　　　self.suit= suit
 　　　　self.hard= hard
 　　　　self.soft= soft
 　　def __repr__( self ):
 　　　　return "{__class__.__name__}(suit={suit!r}, rank={rank!r})".
format(__class__=self.__class__, **self.__dict__)
 　　def __str__( self ):
 　　　　return "{rank}{suit}".format(**self.__dict__)

class NumberCard( Card ):
 　　def __init__( self, rank, suit ):
 　　　　super().__init__( str(rank), suit, rank, rank )

class AceCard( Card ):
 　　def __init__( self, rank, suit ):
 　　　　super().__init__( "A", suit, 1, 11 )

class FaceCard( Card ):
 　　def __init__( self, rank, suit ):
 　　　　super().__init__( {11: 'J', 12: 'Q', 13: 'K' }[rank], suit, 10, 10 )

这是一个基本的不可变对象的类结构。我们还没有实现防止属性更新的特殊方法。我们会在下一章中介绍属性访问。

接下来，我们使用之前定义的类。

>>> c1 = AceCard( 1, '' )
>>> c2 = AceCard( 1, '' )

我们定义了两个看起来一样的Card实例。我们可以用下面的代码获得id()的值。

>>>print( id(c1), id(c2) )
4302577232 4302576976

可以看到，它们的id()值不同，说明它们是两个不同的对象。这正是我们期望的行为。

我们还可以用is运算符检测它们是否相同。

>>>c1 is c2
False

“is测试”基于id()的值，它表明，这两个对象确实是不同的。

我们可以看到，它们的哈希值也是不同的。

>>>print( hash(c1), hash(c2) )
268911077 268911061

这些哈希值是根据id()的值计算出来的。对于继承的方法，这正是我们期望的行为。在这个例子中，我们可以用下面的代码用id()计算出哈希值。

>>>id(c1) / 16
268911077.0
>>>id(c2) / 16
268911061.0

由于哈希值不同，因此它们比较的结果肯定不同。这符合哈希和相等性的定义。但是，这和我们对这个类的预期不同。下面是一个相等性测试。

>>>print( c1 == c2 )
False

我们之前用相等的参数创建了这两个对象，但是它们不相等。在一些应用程序中，这样的行为可能不是所期望的。例如，当统计庄家牌的点数时，我们不想因为使用了6副牌而把同一张牌统计6次。

可以看到，由于我们可以把它们存入set中，因此它们一定是不可变对象。

>>>print( set( [c1, c2] ) )
{AceCard(suit='', rank=1), AceCard(suit='', rank=1)}

这是标准参考库中记录的行为。默认地，我们会得到一个基于对象ID值的__hash__()方法，这样每一个实例都是唯一的。但我们并非总是需要这样的行为。

2.3.3　重载不可变对象

下面是一个重载了__hash__()和__eq__()定义的简单类。

class Card2:
 　　insure= False
 　　def __init__( self, rank, suit, hard, soft ):
 　　　　self.rank= rank
 　　　　self.suit= suit
 　　　　self.hard= hard
 　　　　self.soft= soft
 　　def __repr__( self ):
 　　　　return "{__class__.__name__}(suit={suit!r}, rank={rank!r})".
format(__class__=self.__class__, **self.__dict__)
 　　def __str__( self ):
 　　　　return "{rank}{suit}".format(**self.__dict__)
 　　def __eq__( self, other ):
 　　　　return self.suit == other.suit and self.rank == other.rank
 　　def __hash__( self ):
 　　　　return hash(self.suit) ^ hash(self.rank)
class AceCard2( Card2 ):
 　　insure= True
 　　def __init__( self, rank, suit ):
 　　　　super().__init__( "A", suit, 1, 11 )

原则上，这个对象应该是不可变的。但是，我们还没有引入让它成为真正的不可变对象的机制。在第3章中，我们会探讨如何防止属性值被改变。

同时，请注意，上述代码中省略了上个例子中的两个子类，因为它们的代码和之前一样。

__eq__()方法比较了两个初始值：suit和rank，而没有比较对象中从rank继承而来的值。

21点的规则让这样的定义看起来有些奇怪。在21点中，suit并不重要。那么是不是我们只需要比较rank就可以了？我们是否应该再定义一个方法只比较rank？或者，我们是否应该相信应用程序可以用合适的方式比较rank？对于这3个问题，没有最好的答案，因为这些都是权宜的方法。

hash()方法函数通过对两个基本数字的所有位取异或计算出一种新的位模式。用^运算符是另外一种快速但不好的方法。对于更复杂的对象，最好能使用更合理的方法。在开始自己造轮子之前可以先看看ziplib。

接下来，我们看看这些类的对象是如何工作的。我们预期它们是等价的，并且能够用于set和dict中。以下是两个对象。

>>> c1 = AceCard2( 1, '' )
>>> c2 = AceCard2( 1, '' )

我们定义了两个看起来似乎相同的对象。但是，通过查看ID的值，我们可以确保它们事实上是不同的。

>>>print( id(c1), id(c2) )
4302577040 4302577296
>>>print( c1 is c2 )
False

这两个对象的id()返回值不同。如果用is运算符比较它们，可以看到，它们是两个不同的对象。

接下来，我们比较它们的哈希值。

>>>print( hash(c1), hash(c2) )
1259258073890 1259258073890

可以看到，哈希值是相同的，也就是说它们有可能相等。

==运算符比较的结果和我们预期的一样，它们是相等的。

>>>print( c1 == c2 )
True

由于这两个都是不可变的对象，因此我们可以将它们放进set里。

>>>print( set( [c1, c2] ) )
{AceCard2(suit='', rank='A')}

对于复杂的不可变对象，这样的行为和我们预期的一致。我们必须同时重载这两个特殊方法来使结果一致并且有意义。

2.3.4　重载可变对象

这个例子会继续使用Cards类。可变的牌听起来有些奇怪，甚至是错误的。但是，我们只会对前面的例子做一个小改变。

下面的类层次结构中，我们重载了可变对象的__hash__()和__eq__()。

class Card3:
 　　insure= False
 　　def __init__( self, rank, suit, hard, soft ):
 　　　　self.rank= rank
 　　　　self.suit= suit
 　　　　self.hard= hard
 　　　　self.soft= soft
 　　def __repr__( self ):
 　　　　return "{__class__.__name__}(suit={suit!r}, rank={rank!r})".
format(__class__=self.__class__, **self.__dict__)
 　　def __str__( self ):
 　　　　return "{rank}{suit}".format(**self.__dict__)
 　　def __eq__( self, other ):
 　　　　return self.suit == other.suit and self.rank == other.rank
 　　　　# and self.hard == other.hard and self.soft == other.soft
 　　__hash__ = None
class AceCard3( Card3 ):
 　　insure= True
 　　def __init__( self, rank, suit ):
 　　　　super().__init__( "A", suit, 1, 11 )

接下来，让我们看看这些类对象的行为。我们期望的行为是，它们在比较中是相等的，但是不可以用于set和dict。我们创建了如下两个对象。

>>> c1 = AceCard3( 1, '' )
>>> c2 = AceCard3( 1, '' )

我们再次定义了两个看起来相同的牌。

下面，我们看看它们的ID值，确保它们实际上是不同的两个实例。

>>>print( id(c1), id(c2) )
4302577040 4302577296

和我们预期的一样，它们的ID值不同。接下来，让我们看看是否可以获得哈希值。

>>>print( hash(c1), hash(c2) )
Traceback (most recent call last):
　File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'AceCard3'

因为__hash__被设为None，所以这些用Card3生成的对象不可以被哈希，也就无法通过hash()函数提供哈希值了。这正是我们预期的行为。

我们可以用下面的代码比较这两个对象。

>>>print( c1 == c2 )
True

比较的结果和我们预期的一样，这样我们就仍然可以使用==来比较它们，只是这两个对象不可以存放在set中或者用作dict的键。

下面是当我们试图将这两个对象插入set中时的结果。

>>>print( set( [c1, c2] ) )
Traceback (most recent call last):
　File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'AceCard3'

当试图插入set中时，我们得到了一个适当的异常。

很明显，对于生活中的一些不可变的对象，例如一张牌，这样的定义并不合适。这种定义方式更适合有状态的对象，例如Hand，因为手中的牌时常改变。下面的部分，我们会展示第2个有状态对象的例子。

2.3.5　从可变的Hand类中生成一个不可变的Hand类

如果我们想要统计特定的Hand实例，我们可能希望创建一个字典，然后将一个Hand实例映射为一个计数。在映射中，不能使用一个可变的Hand类作为键。但是，我们可以模仿set和frozenset设计，定义两个类：Hand和FrozenHand。FrozenHand允许我们“冻结”一个Hand类，冻结的版本是不可变的，所以可以作为字典的键。

下面是一个简单的Hand定义。

class Hand:
 　　def __init__( self, dealer_card, *cards ):
 　　　　self.dealer_card= dealer_card
 　　　　self.cards= list(cards)
 　　def __str__( self ):
 　　　　return ", ".join( map(str, self.cards) )
 　　def __repr__( self ):
 　　　　return "{__class__.__name__}({dealer_card!r}, {_cards_str})".format(
 　　　　__class__=self.__class__,
 　　　　_cards_str=", ".join( map(repr, self.cards) ),
 　　　　**self.__dict__ )
 　　def __eq__( self, other ):
 　　　　return self.cards == other.cards and self.dealer_card ==
other.dealer_card
 　　__hash__ = None

这是一个包含适当的相等性比较的可变对象（__hash__是None）。

下面是不可变的Hand版本。

import sys
class FrozenHand( Hand ):
 　　def __init__( self, *args, **kw ):
 　　　　if len(args) == 1 and isinstance(args[0], Hand):
 　　　　　　# Clone a hand
 　　　　　　other= args[0]
 　　　　　　self.dealer_card= other.dealer_card
 　　　　　　self.cards= other.cards
 　　　　else:
 　　　　　　# Build a fresh hand
 　　　　　　super().__init__( *args, **kw )
 　　def __hash__( self ):
 　　　　h= 0
 　　　　for c in self.cards:
 　　　　　　h = (h + hash(c)) % sys.hash_info.modulus
 　　　　return h

不变的版本中有一个构造函数，从另外一个Hand类创建一个Hand类。同时，还定义了一个__hash__()方法，用sys.hash_info.modulus的值来计算cards的哈希值。大多数情况下，这种基于模计算复合对象哈希值的方法能够满足我们的要求。

现在我们可以开始使用这些类了，如下所示。

stats = defaultdict(int)
d= Deck()
h = Hand( d.pop(), d.pop(), d.pop() )
h_f = FrozenHand( h )
stats[h_f] += 1

我们初始化了一个数据字典——stats，作为一个可以存储整数的defaultdict字典。我们也可以用collections.Counter对象作为这个字典。

Hand类冻结后，我们就可以将它用作字典的键，用这个键对应的值来统计实际的出牌次数。