当你拨打`如果键入字典'会发生什么？

Question

我有一个类（我们称之为myClass），它实现了__hash__和__eq__。我也有dict映射myClass对象的某些价值，计算需要一些时间。

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

但是，有时一个新的myClass对象可能等同于较旧的对象（由__eq__方法定义）。因此，不是再次计算该对象的值，我宁愿只查找dict中旧对象myClass的值。要做到这一点，我做if myNewMyClassObj in dict。

我的问题是：

当我使用in条款，什么被调用，__hash__或__eq__？使用dict的关键在于它是O（1）查找时间。那么必须调用__hash__。但是如果__hash__和__eq__不是等效的方法呢？在这种情况下，我会得到if myNewMyClassObj in dict的误报吗？

后续问题：

我希望尽量减少在我dict条目数，所以我非常喜欢仅保留dict一组等效myClass对象之一。如此反复，似乎在计算if myNewClassObj in dict当被称为__eq__需求，这将污秽dict的O（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__在对象处于字典时被调用一次，因为它们都具有不同的散列值，所以一次相等检查足以验证具有该散列值的对象确实是被查询的对象。 __eq__在最后一种情况下未被调用，因为字典中没有任何对象具有与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）中找到它，有时它必须检查所有值。

Answer 3

__hash__定义了对象被放入的桶，__eq__只在对象位于同一个桶时被调用。