Seriously, I have a design problem. I'm (at last!) writing code that
will support arbitrary values as keys for dictionaties. So you will
at last be able to create a dictionary with numeric keys, or with
tuples containing strings and numbers, etc. However, there's a
problem with allowing lists! Since a list can be modified, its value
can be changed later. E.g. if I create a list a = [1, 2] and use it
as a dictionary key, e.g. d = {a: 'foobar'}, and now I call
a.append(3), then the dictionary object is in trouble: it has saved a
*pointer* to a as the key, so the value of d has suddenly changed to
{[1, 2, 3]: 'foobar'}. This is not what you want! (I think :-)
Moreover, the dictionary implementation uses hashing of the keys, and
the entry will still be located at the hash value for [1, 2].
One way out seems to be to make a deep copy of the key value (if it
contains a mutable object), but this is slow. You also have to make
another deep copy when the caller asks for the keys() of the
dictionary, otherwise there would still be a way to subvert the value
of a key... Also note that there may be a list hidden deep inside a
tuple of tuples, so at least some of the the deep copying overhead is
present even when no lists are actually used as keys!
My current solution is to disallow mutable objects as dictionary keys,
unless object comparison is defined as pointer comparison for that
particular object (e.g. files). This makes dictionaries less general,
since lists (or dictionaries!) can't be used as keys. I can imagine
that this is sometimes a drag, but I don't think the performance
penalty of copying is acceptable, nor do I trust the users of
dictionaries never to accidentally modify a list they have used as a
key.
My questions to the general public are:
(1) do you think that disallowing lists as keys is a big drawback?
(2) would you accept the performance penalty of always deep copying
lists used as keys? (2a) when using lists (2b) when not using lists!
(3) do you happen to have another implementation idea?
--Guido van Rossum, CWI, Amsterdam <Guido.van.Rossum@cwi.nl>