Use a copy of mutable objects as dictionary keys

Question

As far as I know python requires an object to be immutable in order to be used as dictionary keys. For example we can't use list as dictionary keys and we have to convert them to tuple first. So what was wrong with making a copy of mutable objects and use the copy as key instead. This way changes to the object doesn't affect the key. Is it because this approach is space inefficient or something else?

Are you asking a question about python internals or soliciting opinions? It is unclear from your question which of the two you want. — Josh J, Dec 04 '15 at 14:20
Using an immutable copy of a mutable object as a key is completely reasonable, as long as you realise that it is the information in the immutable copy that makes it the key it is, and if you change the mutable object it will not match the key you stored. — khelwood, Dec 04 '15 at 14:22
@JoshJ I want to know if there was a specific reason that python prefers using immutable objects instead of making a deep copy of them? — Saeid, Dec 04 '15 at 14:28
Say the list changes what do you then do with the old key->value pair? — shuttle87, Dec 04 '15 at 14:30
@shuttle87 Same thing when we use a tuple of that list, nothing. — Saeid, Dec 04 '15 at 14:41
You're asking why Python doesn't allow you to use mutable objects directly? Because of the way objects are hashed and stored in a hash map for fast access. If the object was mutable, it would need to be rehashed to be correctly stored in the hash map every time it is mutated. That means the dictionary would need to observe all its key objects and keep updating itself when they change. Which is somewhere between super inefficient and madness. — deceze, Dec 04 '15 at 14:45
See: http://stackoverflow.com/questions/14535730/what-do-you-mean-by-hashable-in-python and https://docs.python.org/2/glossary.html#term-hashable — Aske Doerge, Dec 04 '15 at 14:47

Robᵩ · Accepted Answer · 2015-12-04T16:34:18.967

dicts don't accept mutable objects by internally making a deep copy for several reasons, each of which is individually sufficient. Among these reasons are:

1) It would make the overhead of insertion arbitrarily high.

2) It would make the overhead of insertion unpredictable.

3) It would break O(1) lookups.

O(1) lookups are implemented by hashing the keys and using that hash value as an index into a table. This presupposes that a permanent hash can exist for the key.

Consider, in your hypothetical version of Python, this program:

d = { [1,2,3]:"hello" }
for k in d:
    k.append(4)

We are modifying the copied key object of the dict. Obviously the hash must be recomputed, and equally obviously the hash table of d must be recomputed. But when? Or, to anthropomorphize, how does d know that k modified itself? The answer: practically, it can't.

No, if we want an O(1) lookup, we need a hash table. If we want a hash table, we need permanent hash values of keys. If we want permanent hash values of keys, we need immutable objects.

Conversely, if we want mutable keys, we can implement O(logN) lookup. But since Python requires O(1) lookup, we have immutable keys.

score 1 · Answer 2 · answered Dec 04 '15 at 14:49

I think an example will help tou understand:

my_value = 123456
my_string = 'key'

my_dict = {my_string : my_value}

my_string = 'not key anymore!'

print my_dict['key'] #prints : 123456
print my_dict[my_string] # raise KeyError

As you can see the key can still be refenced after the "original" object was modified. But I said "original" because the object wasn't really modified, but a new object was created. That's the meaning of immutable. you can read about it here : https://docs.python.org/2/reference/datamodel.html

If the key was mutable, than the value of the key would be changed as well when I changed the object itself.

score 1 · Answer 3 · answered Dec 04 '15 at 15:37

Because Python does not like to make too much under the hood. When you add an (key, value) item to a dict, the key in the dictionnary and the value are references to the original objects.

Even if the key was a copy of the original object, you could still get a reference to it by iterating the items. And once you get that reference you would be able to change it with all the problems involved...

So the copy method would require that the dict not only take a copy of the key when adding an element, but also consistently returns a new copy in the keys() or items() methods.

Last but not least, as there are mutable and non mutable classes, you can build non copyable classes in Python:

>>> class UnCopy(object):
    def __new__(cls, x, y):
        obj = super(UnCopy, cls).__new__(cls)
        obj.x = x
        obj.y = y
        return obj


>>> c = UnCopy('a', 'b')
>>> d = copy.deepcopy(c)

Traceback (most recent call last):
  File "<pyshell#20>", line 1, in <module>
    d = copy.deepcopy(c)
  File "C:\Python27\lib\copy.py", line 190, in deepcopy
    y = _reconstruct(x, rv, 1, memo)
  File "C:\Python27\lib\copy.py", line 329, in _reconstruct
    y = callable(*args)
  File "C:\Python27\lib\copy_reg.py", line 93, in __newobj__
    return cls.__new__(cls, *args)
TypeError: __new__() takes exactly 3 arguments (1 given)

Anyway, the only real reason is: it is not the way the dict class behaves, not do the other mapping classes from the collection module.

Use a copy of mutable objects as dictionary keys

3 Answers3