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

[lina]

On Thu, Nov 17, 2011 at 10:44 PM, Steven D'Aprano <steve at pearwood.info> wrote:
> 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".
>

Really appreciated for your detailed explaination.

Right now I wanna check which are not hash-able, for strings, set, and
tuple (which I don't understand).

Seems string is hash-able.

Just another quick Q:

>>> basket
['apple', 'pineapple', 'apple', 'pear']

>>> hash(basket[1])
-8771120720059735049
>>> hash(basket[2])
6709291584508918021

>>> print(id(basket))
29215848
>>> print(id(basket[1]))
27389096

What are those numbers means? Sorry,
>
>
> --
> Steven
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>