[Tutor] how to understand unhashable type: 'list'
steve at pearwood.info
Thu Nov 17 15:44:48 CET 2011
>> 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:
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":
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:
If you change just one letter of the string, the hash can change a lot:
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