Dictionary keys in Python

Hello, pythonists!

If you ask what can be key in dictionary a lot of people would say "any immutable type".

But true is it?

If you try to create dictionary with list as key you see error:

Python 3.8.10 (default, Jan 31 1956, 20:18:18)
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> l = []
>>> d = { l: "list" }
Traceback (most recent call last):
? File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'        

Let look closer what happend. TypeError sounds like "unhashable type".

What is a "unhashable type"?

Python contains built-in function `hash()` you could read about this function more here.

Documentation said: "Return the hash value of the object (if it has one)...".

So check type list with `help()` function and you saw next:

?|? Data and other attributes defined here
?|??
?|? __hash__ = None
        

For list `__hash__` method don't have any realization, same situation for any mutable type, but how we could trick Python :0

I don't recommend to use next features of Python language.

Let create class with mutable prop and use it as dict key:

>>> class MyClass
...? ? ?l = []
...?
>>> obj = MyClass()
>>> d = { obj: "                 in dict" }
>>> d
{<__main__.MyClass object at 0x7f0525981490>: 'mutable object as a key in dict'}        

You could modify list and it be the same object:

>>> obj.l.append(1)
>>> obj.l
[1]
>>> obj_ = obj
>>> obj.l[0] = 2
>>> obj
<__main__.MyClass object at 0x7f32eb5849d0>
>>> obj_
<__main__.MyClass object at 0x7f32eb5849d0>
>>> obj_ is obj
True        

So, would you be lying when you say: "a dictionary key can only be of an immutable type"?

Let's figure it out!

What is mutability in Python?

Mutable is when something is changeable or has the ability to change. In Python, ‘mutable’ is the ability of objects to change their values. These are often the objects that store a collection of data.

So, our object is mutable!

But how we can use it as a dictionary key? Do you remember method `__hash__`?

>>> obj.__hash__
<method-wrapper '__hash__' of MyClass object at 0x7f32eb5849d0>        

Try to call it:

>>> obj.__hash__()
8741042095261        

We got the hash of our object, but what is this number, where did it come from, as we found out earlier, the hash of the list could not be obtained. Every object has an `id`, you can check it with `id(obj)`, so answer is: the object hash is calculated as `id(obj) / 16` by default.

>>> hash(obj) == id(obj) / 16
True        

or

>>> hash(id(obj)/16) == hash(obj)
True        

Object ID is integer, you could calculate hash for integer, so all user-defined class with default `__hash__` and `__eq__` could be dictionary key, because they id's hashable.

In conclusion, I hope this article will help you understand some of the basic definitions and mechanisms of the Python language.

...

Article may contain grammatical errors, sorry :(