3

Why are nested dictionaries allowed in Python, while nested sets are disallowed?

One can nest dictionaries and change the sub-dictionaries on the fly, as the following demonstrates:

In [1]: dict1 = {'x':{'a':1, 'b':2}, 'y':{'c':3}}
In [2]: dict2 = {'x':{'a':1, 'b':2}, 'y':{'c':3}}
In [3]: dict1 == dict2
Out[3]: True
In [4]: dict2['x'] = {'d':4}
In [5]: dict1 == dict2
Out[5]: False

On the other hand, if you try to put a set within a set you get an error saying that it can't be done since sets are an "unhashable type":

In [6]: set([set(['a'])])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-8e7d044eec15> in <module>()
----> 1 set([set(['a'])])

TypeError: unhashable type: 'set'

But this doesn't make sense since dictionaries are unhashable too,

In [7]: hash({'a':1})
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-11-44def9788331> in <module>()
----> 1 hash({'a':1})

TypeError: unhashable type: 'dict'

Of course, one can put a frozenset within a set,

In [8]: set([frozenset(['a'])])
Out[8]: {frozenset({'a'})}

but then you can't later change the internals of the nested frozenset like you could for the nested dictionaries.

According to what I've found, set and dict are both implemented with hash tables under the hood, so I don't see why it would be allowed in one case but not the other.

Community
  • 1
  • 1
Nick Alger
  • 984
  • 7
  • 26
  • 3
    Don't see why this is getting downvoted.. It's a geniune question that confuses me, and I've done work on my own to try to figure it out, including trying things on my own and searching for answers online without success. – Nick Alger May 04 '15 at 22:13

2 Answers2

8

The problem is that your examples aren't alike. There is no restriction on the values of a dictionary, only on the keys. Here is a more accurate comparison:

>>> d = {{'a': 'b'}: 'c'}

Traceback (most recent call last):
  File "<pyshell#8>", line 1, in <module>
    d = {{'a': 'b'}: 'c'}
TypeError: unhashable type: 'dict'
>>> s = {{'a': 'b'}, 'c'}

Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    s = {{'a': 'b'}, 'c'}
TypeError: unhashable type: 'dict'

Note that now you get the same behaviour, as expected; you can think of a set as a key-only dict.

You cannot use a mutable/unhashable object as the key in a dictionary or the element in a set because if you changed it in-place it would become unrecoverable (Python matches on __eq__ and __hash__, which is why these methods must be implemented to use a custom class as a key/element). For more on this, see e.g. Why should dictionary keys be immutable? (different language, but same principle - it's all hash tables).

You could also consider watching The Mighty Dictionary if you're interested in the topic.

Community
  • 1
  • 1
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
  • Oh, I see. I think my confusion was due to a misunderstanding of the set dictionary implementation. I was thinking of set elements as being values of the underlying dict, rather than keys. – Nick Alger May 04 '15 at 23:51
  • @NickAlger: In the old days, before we had `set`, we had to implement `{1, 2, 3}` as `{1: None, 2: None, 3: None}`, so old people tend to forget that it's not obvious that the set elements are keys. :) But if you think about it, none of the advantages of set (instant lookup, disallowing duplicates, etc.) make sense unless the elements are keys. – abarnert May 05 '15 at 19:20
2

Since the hash of an element must be unique for its lifetime in order to be meaningfully stored in a hash table, a set (as well as a list) can't be a member of a set, as you have observed. However, in a dict, the object which gets hashed is the key, not the value. Hence this is legal:

{'x': {1, 2, 3}}  #  a string is hashable

and this is not:

{{1, 2, 3}: 'x'}

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-1-1cd059738afd> in <module>()
----> 1 {{1, 2, 3}: 'x'}
TypeError: unhashable type: 'set'

This is true for other unhashable types too (list and dict for instance).

ConsideredHarmless
  • 116
  • 3