[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
More information about the Tutor
mailing list