Python __hash__：身份验证与等价性

Question

我有一个类，它的实例需要通过与其所携带数据值不同的标识来进行区分。在我的代码中，我打算使用==表示两个实例在数据方面是等价的，并使用is表示两个变量引用同一个实例，即它们是相同的。在我看来，这都很正常。

此外，我想在set和dict中使用实例（无论是否等价）作为键。这需要为该类定义__hash__函数。

但在这方面，我不理解__hash__的要求：

仅需要保证相等的对象具有相同的哈希值。

这是否意味着不能将两个不同但等效的对象用作dict中不同的键，或者在set中单独出现？ 在下面的代码中，我通过重载__eq__和__hash__来反映我的预期使用情况而违反了这一要求。它在Python 2.7和3.7中按预期工作。

如果像我这样违反__hash__的要求会有什么负面影响？

有更好的方法来实现我的目标吗？

class A( object ):
        def __init__( self, v1, v2 ):
                self.v = ( v1, v2 )

        def __eq__( self, b ):
                return self.v[0] == b.v[0] and self.v[1] == b.v[1]

        def __hash__( self ):
                return id( self )

        def __str__( self ):
                return str( self.v )

p = A( 1, 0 )
q = A( 1, 0 )

print( str( p ), str( q ) )
print( "identical?", p is q )
print( "equivalent?", p == q )
print( "hashes", hash(p), hash(q) )

s = set( [p, q] )
print( "set length", len( s ) )
print( "both in set?", p in s, q in s )

d = { p:3, q:4 }
print( "dict length", len( d ) )
print( "as distinct keys", d[p], d[q] )

- Steve White

---

你的例子展示了问题。尽管p和q被认为是相等的，但在集合和字典中它们是不同的。d[A(1, 0)]很可能是一个键错误，即使有（两个！）与该值匹配的键。请注意，既没有使用__eq__也没有使用__hash__来确定身份，您不能覆盖id的结果。 - jonrsharpe

如果__eq __()返回True，则__hash __() 必须为两个对象返回相同的值，否则dict/set永远不会调用这些对象上的__eq __()。 - jasonharper

你必须问自己：“如果对象是相等的，为什么我需要它们都出现在集合中作为不同的元素？” 正确的答案将是“我真的不需要它”。 - sanyassh

嗨@jonsharpe，我想你误解了。 我不打算查找A的新实例。 就像我的示例一样，我创建一个A，将其放入集合或字典中，然后稍后通过标识而不是值查找它。 我编写的代码似乎正是这样做的，并产生我期望的结果。 - Steve White

嗨@sanhash。我不明白你的意思。在什么意义上，集合和字典是无用的？我可以向它们添加A对象，我可以在字典中查找并检索它们。我可以从集合中弹出它们。这些都是我想要做的事情。你有什么用途，我没有列出来的吗？ - Steve White

Answer 1

唯一必需的属性是相等的对象具有相同的哈希值。

“规范文本中的‘比较相等’是指它们的__eq__方法的结果——没有要求它们是同一个对象。”

“__hash__”必须基于在“__eq__”中使用的值，而不是对象的“id”——你代码中这部分是错误的。为了让它工作，它必须是这样的：

只需要执行：

      ...
      def __eq__( self, b ):
           return self.v[0] == b.v[0] and self.v[1] == b.v[1]

      def __hash__( self ):
           return hash((self.v[0], self.v[1]))

这是否意味着两个不同但等价的对象不能用作字典中的不同键，或者单独出现在集合中？

是的。这就是规范的含义。

解决方法是保留类的默认__eq__实现以符合规则，并实现一种替代比较形式，在代码中使用它。

最简单的方法是保留__eq__的默认实现，即按标识比较，并使用任意方法进行比较（在不支持运算符重载的语言中，代码必须使用的习惯用法）：

class A( object ):
    ...
    def equals( self, b ):
       return self.v[0] == b.v[0] and self.v[1] == b.v[1]

p = A( 1, 0 )
q = A( 1, 0 )

print( str( p ), str( q ) )
print( "identical?", p is q )
print( "equivalent?", p.equals(q) )

有一些方法可以稍微改善这个问题 - 但基本线是：__eq__必须符合规则，并进行身份比较。

一种方法是拥有一个内部关联对象，它作为一个“命名空间”，您可以用于比较：

class CompareSpace:
    def __init__(self, parent):
        self.parent = parent

        def __eq__( self, other ):
            other = other.parent if isinstance(other, type(self)) else other 
            return self.parent.v[0] == other.v[0] and other.v[1] == b.parent.v[1]


    class A:
        def __init__( self, v1, v2 ):
            self.v = ( v1, v2 )
            self.comp = CompareSpace(self)

        def __str__( self ):
            return str( self.v )

p = A( 1, 0 )
q = A( 1, 0 )

print( str( p ), str( q ) )
print( "identical?", p is q )
print( "equivalent?", p.comp == q )
print( "hashes", hash(p), hash(q) )

破碎演示

现在我将插入一个更加破碎的类的例子，以确保问题在第一次尝试时出现。但是，即使问题每200万次发生一次，你的代码仍然无法用于任何真实的应用，即使是个人代码：你将拥有一个不确定性的字典：

class Broken:
    def __init__(self, name):
        self.name = name
    def __hash__(self):
        return id(self) % 256
    def __eq__(self, other):
        return True
    def __repr__(self):
        return self.name


In [23]: objs = [Broken(f"{i:02d}") for i in range(64)]                                        

In [24]: print(objs)                                                                           
[00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63]

In [25]: test = {}                                                                             

In [26]: for obj in objs: 
    ...:     if obj not in test: 
    ...:         test[obj] = 0 
    ...:                                                                                       

In [27]: print(test)                                                                           
{00: 0, 01: 0, 02: 0, 11: 0}

# Or with simple, unconditional, insertion:
In [29]: test = {obj: i for i, obj in enumerate(objs)}                                         

In [30]: test                                                                                  
Out[30]: {00: 57, 01: 62, 02: 63, 11: 60}

（我再次强调，虽然您的值本身不会发生冲突，但内部字典代码必须将哈希中的数字减少到其哈希表中的索引 - 不一定是通过模（％） - 否则每个空字典都需要2 ** 64个空条目，仅当所有哈希值仅为64位宽时才需要。）

- jsbueno

---

显然我表达不清楚。我呈现的代码实现了我的意图。 你的代码实现了我不想要的功能。就好像... 我们是否同意等价和恒等是两个不同的概念？ - Steve White

所以，答案是“不行”，你不能让相等的对象在集合或字典键中具有不同的哈希值。我建议你保留默认的__eq__方法，它通过“id”进行比较，并使用手动比较方法来比较你的数据（你将失去“==”运算符，但可以编写一个if obj_a.eq(obj_b):的语句）。 - jsbueno

我修改了答案，以便您能够得到更好的服务。另一个选项是使用包装器，就像@MSeifert的答案中所示，而不是使用内部关联对象 - 无论哪种方式，您都需要一个辅助类才能使用==。 - jsbueno

嗨，jsbueno。问题不是“是否允许”。我考虑过将'=='留下来表示与“is”相同的意思，并编写其他函数以正确区分等价性和身份 - 但是这似乎是错误的，考虑到这些运算符的通常定义，以及我编写的代码似乎正好做到了我想要的。再次强调：像我所写的代码这样的负面后果到底是什么？我们还没有看到这方面的例子。 - Steve White

我添加了一个实时示例，展示了那里发生的事情。 - jsbueno

Answer 2

我已经进行了更多的测试。结果是，尽管缺乏文档，尽管警告可能出现问题，

我编写的代码从未失败过。

我现在已经在64位和32位平台上使用CPython 2.7、Python 3.0和PyPy，向dict和set中添加了数十亿个对象。我曾经在一台更大的机器上尝试过，同时向单个set中添加了超过20亿个对象。它完美地工作了。我从未看到OP中呈现的代码发生碰撞。

这不是偶然或意外。

有人费力确保了这种行为。谜团是，为什么没有记录它？

通过其他帖子我得出的最好结论是，容器算法以某种方式丢失了OP类A中id()函数保证的唯一性，当发生这种情况时，就会发生碰撞，并调用__eq__。

这可能会发生在某些平台和Python的一些实现中。但是在我尝试过的每个地方，它从未发生过。

可能与一些未记录的属性有关：对于任何类实例obj，

hash( id( obj ) ) == hash( obj )
# and
hash( hash( obj ) ) == hash( obj )

实际上，hash(id(x))并不总是等于hash(x)。试试x=-2。事实上，对于对象实例obj，hash(obj)==id(obj) >> 16。但这让我觉得可能取决于实现。

为了查看代码何时或如何会出错，我使用下面的代码进行了测试。思路是，如果A的某个实例与新实例发生冲突，它将无法放入集合中，因为__eq__无法打破平局。此代码检查是否曾经发生过这种情况。我从未见过这种情况。请自行尝试，并告诉我您使用的操作系统和Python版本！

请注意——您可能会耗尽所有系统资源并使计算机崩溃。打开控制台并在其中运行top，以查看发生了什么。使用OP定义的class A：

from __future__ import print_function
from sys import stdout

class A( object ):
    def __init__( self, v1, v2 ):
            self.v = ( v1, v2 )

    def __eq__( self, b ):
            return self.v[0] == b.v[0] and self.v[1] == b.v[1]

    def __hash__( self ):
            return id( self )

    def __str__( self ):
            return str( self.v )

NINSTANCES = 3000000    # play with this number -- carefully!
STATUS_INTERVAL = 100000

def test():
        """ hammer the set algorithms """
        s = set()
        instances = []
        for i in range( 0, NINSTANCES ):
                p = A( 1, 0 )
                s.add( p )
                instances.append( p )
                if not i % STATUS_INTERVAL:
                        stdout.write( str( i // STATUS_INTERVAL ) + " " )
                        stdout.flush()
        stdout.write( "\n" )

        print( "length of set", len( s ) )
        print( "number of instances", len( instances ) )

        for i in instances:
                if not i in s:
                        print( "INSTANCE DROPPED OUT!" )
test()

- Steve White

---

为什么在查找时要使用数据哈希（而不是__hash__）？这是因为某些情况下，原始键对象不可用，特别是如果容器要存储在程序运行时间之后。然后，仍然可以使用新的、某种程度上“等效”的键来检索项目。然而，这不是 OP 中代码预期的用例。我想知道是否有一种方法可以支持两种情况，而不放弃“等价”的==操作符的含义？ - Steve White