[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?


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 

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")
py> hash("Susan")

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

py> hash("abcdef")
py> hash("bbcdef")

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".


More information about the Tutor mailing list