Why can't a set store mutable data types?

user_8055025 0
Viewed 323

I read in a book which stated due to "algorithmic underpinnings", only instances of immutable types can be added to a Python set, but it did not explain what are those "algorithmic underpinnings".

After trying to actually add a list (mutable data type) to set, I got an error saying TypeError: unhashable type: list, but again why does the item to be added has to be hashable?

>>> my_set = set()
>>> my_set.add('a')
>>> my_set.add(1)
>>> my_set.add((1,2,3))
>>> my_set.add([1,2,3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
data-structures python
1 Answers

From the Python documentation:

A set object is an unordered collection of distinct hashable objects

and

An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() method). Hashable objects which compare equal must have the same hash value.

To explain what that means, sets/dictionary are based on the concept of Hash Tables, where all the keys are stored not with their actual value, but with their hash. The hash is an integer number that is calculated from the key value.

For example, if I want to insert the key k="Hello" into a set with the hashing function f(k) = sum of all ASCII values, then you would get Hash of k = f(k) = 72+101+108+108+111 = 500, and you would store k in position 500 (Of course it's much more complicated than this, it's just a stupid example).

This way when you want to check if k is in the set, you don't have to do a linear search, but you can calculate its hash and check at index 500 if there is something, so it's much faster. (That's why sets are much faster than lists when they have many elements).

Little problem: if your key is a list, you can modify it, and that would change its hash, so each time you modify the list you would need to edit all the sets/dictionaries that contains it, and it would be a huge mess, so It's better to avoid mutable types, and that's why lists are not hashable.

user_108066420
Related