list vs tuple

[Ken Seehof]

Mark Pilgrim <f8dy at yahoo.com> asked:


> It was my understanding that only tuples containing immutable objects
could
> be used as dictionary keys.  For instance, (1,2,3) can be, and
("a","b","c")
> can be, but ([1,2,3], ["a","b","c"]) can not, because the underlying
objects
> could mutate and cause problems.  (Wow, that sounds like a bad sci-fi
> movie.)  Is this true?
>
> -M
> You're smart; why haven't you learned Python yet?
> http://diveintopython.org/

Exactly.  Suppose python didn't have that rule:

>>> a = [1,2]
>>> d = {}
>>> d[a] = 'parrot'  # in the real world this raises an exception
>>> a[0] = 5

Lets assume for the moment that we don't change the fact that keys are
inserted by reference.  Now in order to make things work, python would have
to rehash d[a].  This is a problem because python doesn't keep track of who
else is referencing the list object attached to the name 'a'.  Since
dictionaries store references as keys, so the object named 'a' and the
dictionary index to 'parrot' are the same object.  Some kind of very complex
scheme would have to be devised to tell the dictionary to rehash keys when
they get modified.

A rather extraordinarily bad alternative would be copy (deep copy) the key
when assigning into a dictionary, thereby attempting to keep the keys safe
from modification (this would mean the keys() and items() methods would have
to do a deep copy too).  It gets worse.  Dictionary keys would have to be
limited to objects that have a deep copy protocol.  Of course the
performance issues would be a nightmare.  Now I have a headache.  &-(

Considering the alternatives, the constaint that dictionary keys must be
immutable is quite elegant.

- Ken Seehof
kseehof at neuralintegrator.com
www.neuralintegrator.com