Menu
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
712
If we try to access the value of key that does not exist in the dictionary, then it will raise KeyError. This can also be a way to check if exist in dict or not i.e. Here it confirms that the key 'test' exist in the dictionary.
You can check if a key exists in a dictionary using the keys() method and IN operator. What is this? The keys() method will return a list of keys available in the dictionary and IF , IN statement will check if the passed key is available in the list. If the key exists, it returns True else, it returns False .
Checking if key exists using the get() method The get() method is a dictionary method that returns the value of the associated key. If the key is not present it returns either a default value (if passed) or it returns None.
In such instances, if the user tries to access a missing key, an error is popped indicating missing keys.
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.
51
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
