6

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

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

但是，有时新myClass对象可能等同于旧对象（由__eq__方法定义）。因此，与其再次计算该对象的值，我宁愿只myClass在dict. 为了做到这一点，我做到了if myNewMyClassObj in dict。

这是我的问题：

当我使用该in子句时，会调用什么，__hash__或者__eq__？使用 a 的重点dict是它的 O(1) 查找时间。所以 then__hash__必须被调用。但是如果不是等价的方法呢__hash__？__eq__在这种情况下，我会得到误报if myNewMyClassObj in dict吗？

跟进问题：

我想尽量减少dict我myClass的dict. 再一次，似乎__eq__需要在计算时调用if myNewClassObj in dict，这会将 adict的 O(1) 查找时间污染为 O(n) 查找时间

4

3 回答 3

8

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

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

因此，您只需要确保两者__eq__都__hash__快速。

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

请注意，__eq__仅在具有相同哈希并分配给相同存储桶的对象上调用。此类对象的数量通常非常少（dict实现可以确保这一点）。所以你仍然有（大致）O(1)查找性能。

于 2012-10-21T20:38:58.563 回答
7

__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__在最后一种情况下没有调用，因为 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 需要显式检查字典中所有值的相等性，直到找到相等的值（或发现它们都不等于它正在寻找的一个）。有时它会在第一次尝试时找到它（Foo(1) in dict上面），有时它必须检查所有值。

于 2012-10-21T20:38:06.787 回答
1

__hash__ 定义了对象放入的桶， __eq__ 仅当对象在同一个桶中时才被调用。

于 2012-10-21T20:38:07.597 回答