当你调用`if key in dict`时会发生什么 [英] What happens when you call `if key in dict`

问题描述

我有一个类（我们称之为 myClass ）实现 __哈希__ 和 __eq __ 。我还有一个 dict 将 myClass 对象映射到某种值，计算需要一些时间。

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

然而，有时候新的 myClass 对象可能等同于较旧的（由 __ eq __ 方法定义）。因此，不要再次计算该对象的值，我宁愿只在 dict myClass 对象的值C>。为了达到这个目的，如果在dict中的myNewMyClassObj在中，那么我做。

这是我的问题：

当我在子句中使用时，调用什么， __ hash __ 或 __当量__ ？使用 dict 的观点是它是O（1）查找时间。所以必须调用 __ hash __ 。但是如果 __ hash __ 和 __ eq __ 不是等效的方法呢？在这种情况下，如果在中的myNewMyClassObj？

跟进问题： p>

我想最小化我的 dict 中的条目数量，所以我最好只保留一个集合在 dict 中的等价物 myClass 对象。所以再一次，似乎在计算时需要调用 __ eq __ ，如果dict中的myNewClassObj ，那么这将污染一个 dict 的O（1）查找时间到O（n）查找时间

解决方案

首先，调用 __ hash __（myNewMyClassObj）。如果没有在字典中找到具有相同散列的对象，则Python假定 myNewMyClassObj 不在字典中。 （请注意，Python要求每当 __ eq __ 评估为两个对象相等时，它们的 __ hash __ 必须相同。 p>

如果在字典中找到一些具有相同 __ hash __ 的对象， __ eq __ 每个都被调用。如果 __ eq __ 评估为任何一个相等，则dict _ 中的 myNewMyClassObj将返回True。

因此，您只需要确保 __ eq __ 和 __哈希__ 都很快。

对于您的跟进问题：是的， dict _ 仅存储一组等效的 MyClass 对象（由 __ eq __ 定义）。 （正如设置）

请注意，只有具有相同哈希值的对象才调用 __ eq __ 分配到同一个桶。这样的对象的数量通常是非常小的数字（ dict 实现确保）。所以你还有（大概） O（1）查询性能。

I have a class (let's call it myClass) that implements both __hash__ and __eq__. I also have a dict that maps myClass objects to some value, computing which takes some time.

Over the course of my program, many (in the order of millions) myClass objects are instantiated. This is why I use the dict to keep track of those values.

However, sometimes a new myClass object might be equivalent to an older one (as defined by the __eq__ method). So rather than compute the value for that object again, I'd rather just lookup the value of older myClass object in the dict. To accomplish this, I do if myNewMyClassObj in dict.

Here's my question:

When I use that in clause, what gets called, __hash__ or __eq__? The point of using a dict is that it's O(1) lookup time. So then __hash__ must be called. But what if __hash__ and __eq__ aren't equivalent methods? In that case, will I get a false positive for if myNewMyClassObj in dict?

Follow up question:

I want to minimize the number of entries in my dict, so I would ideally like to keep only one of a set of equivalent myClass objects in the dict. So again, it seems that __eq__ needs to be called when computing if myNewClassObj in dict, which would defile a dict's O(1) lookup time to an O(n) lookup time

解决方案

First, __hash__(myNewMyClassObj) gets called. If no object with the same hash is found in the dictionary, Python assumes myNewMyClassObj is not in the dictionary. (Note that Python requires that whenever __eq__ evaluates as equal for two objects, their __hash__ must be identical.)

If some objects with the same __hash__ are found in the dictionary, __eq__ gets called on each of them. If __eq__ evaluates as equal for any of them, the myNewMyClassObj in dict_ returns True.

Thus, you just need to make sure both __eq__ and __hash__ are fast.

To your follow up question: yes, dict_ stores only one of a set of equivalent MyClass objects (as defined by __eq__). (As does set.)

Note that __eq__ is only called on the objects that had the same hash and got allocated to the same bucket. The number of such objects is usually a very small number (dict implementation makes sure of that). So you still have (roughly) O(1) lookup performance.

这篇关于当你调用`if key in dict`时会发生什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！