python - What makes lists unhashable?

Question

So lists are unhashable:

>>> { [1,2]:3 }
TypeError: unhashable type: 'list'

The following page gives an explanation:

A list is a mutable type, and cannot be used as a key in a dictionary (it could change in-place making the key no longer locatable in the internal hash table of the dictionary).

I understand why it is undesirable to use mutable objects as dictionary keys. However, Python raises the same exception even when I am simply trying to hash a list (independently of dictionary creation)

>>> hash( [1,2] )
TypeError: unhashable type: 'list'

Does Python do this as a guarantee that mutable types will never be used as dictionary keys? Or is there another reason that makes mutable objects impossible to hash, regardless of how I plan to use them?

Answer 1

Dictionaries and sets use hashing algorithms to uniquely determine an item. And those algorithms make use of the items used as keys to come up the unique hash value. Since lists are mutable, the contents of a list can change. After allowing a list to be in a dictionary as a key, if the contents of the list changes, the hash value will also change. If the hash value changes after it gets stored at a particular slot in the dictionary, it will lead to an inconsistent dictionary. For example, initially the list would have gotten stored at location A, which was determined based on the hash value. If the hash value changes, and if we look for the list we might not find it at location A, or as per the new hash value, we might find some other object.

Since, it is not possible to come up with a hash value, internally there is no hashing function defined for lists.

PyObject_HashNotImplemented,                /* tp_hash */

As the hashing function is not implemented, when you use it as a key in the dictionary, or forcefully try to get the hash value with hash function, it fails to hash it and so it fails with unhashable type

TypeError: unhashable type: 'list'