当你调用`if key in dict`时会发生什么

Question

我有一个类(让我们称之为myClass)实现两者__hash__和__eq__.我也有一个dict将myClass对象映射到某个值,计算需要一些时间.

在我的程序过程中,许多(大约数百万)myClass对象被实例化.这就是我使用它dict来跟踪这些值的原因.

但是,有时新myClass对象可能等同于旧对象(由__eq__方法定义).因此,我不是再次计算该对象的值,而是仅查找旧myClass对象的值dict.要做到这一点,我做到了if myNewMyClassObj in dict.

这是我的问题:

当我使用该in子句时,会调用什么,__hash__或者__eq__？使用a的关键dict是它是O(1)查找时间.所以__hash__必须要打电话.但是,如果__hash__和__eq__不是等价的方法呢？在那种情况下,我会得到误报if myNewMyClassObj in dict吗？

跟进问题:

我想最小化我的条目数dict,所以我最好只保留一组等效myClass对象中的一个dict.再次,似乎__eq__需要在计算时调用if myNewClassObj in dict,这会将dictO(1)查找时间玷污为O(n)查找时间

Answer 1

首先,__hash__(myNewMyClassObj)被召唤.如果在字典中找不到具有相同散列的对象,则Python假定myNewMyClassObj不在字典中.(请注意,Python要求每当__eq__两个对象的求值相等时,它们__hash__必须相同.)

如果__hash__在字典中找到了一些具有相同对象的对象,则会__eq__在每个对象上调用它们.如果__eq__对它们中的任何一个求值相等,则myNewMyClassObj in dict_返回True.

因此,您只需确保两者__eq__并且__hash__速度很快.

对于你的后续问题:是的,dict_只存储一组等效MyClass对象中的一个(由定义__eq__).(确实如此.)

请注意,__eq__仅在具有相同哈希的对象上调用并分配给同一个存储桶.这些对象的数量通常是非常小的数量(dict实现确保这一点).所以你仍然有(大致)O(1)查找性能.

Answer 2

__hash__将永远被称为; __eq__如果对象确实在字典中,或者如果具有相同散列的另一个对象在字典中,则将调用.哈希值用于缩小可能键的选择范围.密钥按哈希值分组为"桶",但是对于查找,Python仍然必须检查桶中的每个密钥是否与查找密钥相等.请参阅http://wiki.python.org/moin/DictionaryKeys.看看这些例子:

>>> class Foo(object):
...     def __init__(self, x):
...         self.x = x
...     
...     def __hash__(self):
...         print "Hash"
...         return hash(self.x)
... 
...     def __eq__(self, other):
...         print "Eq"
...         return self.x == other.x
>>> Foo(1) in d
Hash
Eq
10: True
>>> Foo(2) in d
Hash
Eq
11: True
>>> Foo(3) in d
Hash
Eq
12: True
>>> Foo(4) in d
Hash
13: False

在该示例中,您可以看到__hash__始终被调用. __eq__当对象在dict中时,每次查找都会调用一次,因为它们都具有不同的哈希值,因此一次相等性检查足以验证具有该哈希值的对象确实是被查询的对象. __eq__在最后一种情况下没有调用,因为dict中没有任何对象具有相同的哈希值Foo(4),因此Python不需要继续使用__eq__.

>>> class Foo(object):
...     def __init__(self, x):
...         self.x = x
...     
...     def __hash__(self):
...         print "Hash"
...         return 1
... 
...     def __eq__(self, other):
...         print "Eq"
...         return self.x == other.x
>>> d = {Foo(1): 2, Foo(2): 3, Foo(3): 4}
Hash
Hash
Eq
Hash
Eq
Eq
>>> Foo(1) in d
Hash
Eq
18: True
>>> Foo(2) in d
Hash
Eq
Eq
19: True
>>> Foo(3) in d
Hash
Eq
Eq
Eq
20: True
>>> Foo(4) in d
Hash
Eq
Eq
Eq
21: False

在此版本中,所有对象都具有相同的哈希值.在这种情况下__eq__总是被调用,有时多次调用,因为散列不区分值,因此Python需要显式检查dict中所有值的相等性,直到找到相等的值(或者发现它们都不等于一个它正在寻找).有时它会在第一次尝试时找到它(Foo(1) in dict上图),有时它必须检查所有值.