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

[Steven D'Aprano]

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