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

Question

我有一个类（我们称之为myClass），它同时实现了__hash__和{}。我还有一个dict，它将myClass对象映射到某个值，计算需要一些时间。在

在我的程序过程中，许多（以百万计）myClass对象被实例化。这就是为什么我使用dict来跟踪这些值。在

但是，有时新的myClass对象可能与旧对象等价（由__eq__方法定义）。因此，与其再次计算该对象的值，不如在dict中查找旧的myClass对象的值。为了完成这个任务，我做了if myNewMyClassObj in dict。在

我的问题是：

当我使用那个in子句时，什么叫__hash__或{}？使用dict的关键在于它是O（1）查找时间。所以必须调用__hash__。但是如果__hash__和{}不是等价的方法呢？在这种情况下，我会得到if myNewMyClassObj in dict的假阳性吗？在

后续问题：

我想最小化我的dict中的条目数，因此理想情况下，我希望在dict中只保留一组等价的myClass对象中的一个。因此，在计算__eq__时似乎需要调用__eq__，这将把dict的O（1）查找时间污损为O（n）查找时间

Answer 1

将始终调用__hash__；__eq__如果对象确实在字典中，或者如果字典中有另一个具有相同哈希的对象，则将调用__eq__。散列值用于缩小可能键的选择范围。这些键按哈希值分组到“bucket”中，但是对于lookup，Python仍然必须检查bucket中的每个键是否与lookup key相等。见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__。^当对象在dict中时，每次查找都会调用一次{}，因为它们都有不同的哈希值，因此一次相等性检查就足以验证具有该哈希值的对象确实是被查询的对象。__eq__在最后一个例子中没有调用，因为dict中没有一个对象具有与Foo(4)相同的哈希值，因此Python不需要继续使用__eq__。在

^{pr2}$

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

Answer 2

首先，__hash__(myNewMyClassObj)被调用。如果在字典中找不到具有相同哈希的对象，Python假定myNewMyClassObj不在字典中。（请注意，Python要求每当两个对象的__eq__计算结果为相等时，它们的__hash__必须相同。）

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

因此，您只需要确保__eq__和{}都很快。在

对于您的后续问题：是，dict_只存储一组等价的MyClass对象（由__eq__定义）中的一个。（正如设定的那样。）

注意，__eq__只对具有相同哈希并分配给同一个bucket的对象调用。这类对象的数量通常很小（dict实现确保了这一点）。因此，您仍然（大致上）具有O(1)查找性能。在

Answer 3

定义对象放入的bucket，只有当对象在同一个bucket中时才会调用。在