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

Question

我有一个实现了 __hash__ 和 __eq__ 的类(我们称它为 myClass)。我还有一个 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 中的条目数，因此理想情况下，我希望在 中只保留一组等效的 myClass 对象中的一个字典。因此，在计算 if myNewClassObj in dict 时，似乎需要调用 __eq__，这会破坏 dict 的 O(1)查找时间到 O(n) 查找时间

Answer 1

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

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

因此，您只需要确保 __eq__ 和 __hash__ 都很快。

对于您的后续问题:是的，dict_ 仅存储一组等效的 MyClass 对象(由 __eq__ 定义)中的一个。 (和设置一样。)

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