What does the == operator actually do on a Python dictionary?

Question

Consider:

>>> a = {'foo': {'bar': 3}} >>> b = {'foo': {'bar': 3}} >>> a == b True 

According to the python doc, you can indeed use the == operator on dictionaries.

What is actually happening here? Is Python recursively checking each element of the dictionaries to ensure equality? Is it making sure the keys are identically matched, and the values are also identically matched?

Is there documentation that specifies exactly what == on a dictionary means? Or whether I have to implement my own version of checking for equality?

(If the == operator works, why aren't dicts hashable? That is, why can't I create a set() of dicts, or use a dict as a dictionary key?)

Answer 1

Python is recursively checking each element of the dictionaries to ensure equality. See the C dict_equal() implementation, which checks each and every key and value (provided the dictionaries are the same length); if dictionary b has the same key, then a PyObject_RichCompareBool tests if the values match too; this is essentially a recursive call.

Dictionaries are not hashable because their __hash__ attribute is set to None, and most of all they are mutable, which is disallowed when used as a dictionary key.

If you were to use a dictionary as a key, and through an existing reference then change the key, then that key would no longer slot to the same position in the hash table. Using another, equal dictionary (be it equal to the unchanged dictionary or the changed dictionary) to try and retrieve the value would now no longer work because the wrong slot would be picked, or the key would no longer be equal.

Answer 2

From docs:

Mappings (dictionaries) compare equal if and only if their sorted (key, value) lists compare equal .[5] Outcomes other than equality are resolved consistently, but are not otherwise defined. [6]

Footnote [5]:

The implementation computes this efficiently, without constructing lists or sorting.

Footnote [6]:

Earlier versions of Python used lexicographic comparison of the sorted (key, value) lists, but this was very expensive for the common case of comparing for equality. An even earlier version of Python compared dictionaries by identity only, but this caused surprises because people expected to be able to test a dictionary for emptiness by comparing it to {}.