[Tutor] how to understand unhashable type: 'list'

Steven D'Aprano steve at pearwood.info
Thu Nov 17 15:44:48 CET 2011

```lina wrote:

>> You are trying to store a list as a key inside a dict. This cannot be done
>> because lists (like all mutable types) can't be hashed.
>
> I checked online dictionary, still confused about hashed. is it equal
> to mix together or mess together?

Almost.

In ordinary English, a hash is a mixed up mess. For example, "hash
browns" are fried mashed potato.

In computing, a hash got its name by analogy with "mixed up". A hash is
short for "hash table".

An ordinary table might look something like this:

Position  Value
1         "Fred"
2         "Barney"
3         "George"
4         "Betty"
5         "Mary"
6         *unused*
7         *unused*
8         *unused*
9         *unused*

To find whether "Mary" is in the table, you have to start at position 1,
and inspect each value to see whether it equals "Mary":

for position 1 to 9:
if value at position == "Mary": print FOUND

If there are many items, this will be slow. But here's a faster way,
using a "hash table":

Position  Value
1         *unused*
2         "Barney"
3         *unused*
4         "Betty"
5         *unused*
6         *unused*
7         "Fred"
8         "Mary"
9         "George"

Take the string "Mary", and mix it up into a "hash value" between 1 and
9. In this case, you will get 8. Look in position 8, and you will find
"Mary".

Take the string "Susan" and mix it up into a hash value. In this case,
you might get 3. Since position 3 is actually unused, you know that
"Susan" is not in the hash table.

All the hard work is done in the "mixing" of the string. This is called
a hash function, and Python already has one:

py> hash("Mary")
-1963774307
py> hash("Susan")
92926151

If you change just one letter of the string, the hash can change a lot:

py> hash("abcdef")
-33722981
py> hash("bbcdef")
-508939398

But lists are not hashable, because they are mutable (can be changed):

py> hash([1, 2, 3])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Python dictionaries are hash tables. You could have a million items in a
dict, and to check whether "Mary" is one of them with a list would
require you to check all one million items. But with a dict, Python
hashes the string to get a number, then reduces that number to fit
within the range of positions in the dict, then looks immediately in the
right spot to find "Mary".

--
Steven
```