2

All -

I have a very basic question today ... but it has been preventing me from moving on productively in my programming, so I am posting it here.

I want to create a dictionary that takes a dictionary as a key. Presumably I can only pass a reference to the dictionary as key ... only I don't know how to do that in Python. Here is a toy reduction of what I am trying to do:

def test( dict ):
    a={}
    b={1:1}
    a[ dict ] = b
    return a

a = {0:0}
print test( a )

I would like b to be a dictionary of the form { {0:0} : {1:1} }.

Any help with this is much appreciated.

Kind regards -

Pat

Pat
  • 353
  • 1
  • 4
  • 15

5 Answers5

2

Keys for dictionaries must be hashable items; unfortunately, dictionaries themselves are not hashable (they are mutable, which disqualifies them from being hashable).

Use their item list, converted to a sorted tuple, instead:

a[tuple(sorted(dct.items()))] = b

Mutable objects are not hashable because they can be changed in-place, making later key-lookups fail. What would the expected outcome be if you added or removed items from the dictionary you used as the key, for example?

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • 2
    Sadly, this won't work exactly as required, because the order of `dct.items()` might vary, leading to index errors. – orlp Aug 21 '12 at 18:49
  • @nightcracker: in most cases, the order of the same set of key/value pairs would be returned in the same order. If you insert, then remove a lot of keys, then insert again, you *could* loose that ordering though, so I'll add some sorting. – Martijn Pieters Aug 21 '12 at 18:51
  • Sorting is an inadequate solution for this, considering it's `O(n log n)` complexity (while hashing each element requires only `O(n)`), as well as requiring the elements be sortable (which is an unnecessary requirement in addition to being hashable). See the frozendict implementation I link in my answer. – orlp Aug 21 '12 at 18:52
  • @nightcracker: Generally speaking using `dict` as a key is suspect in the first place and needs some rethinking. The rest of my answer (why doesn't this work) is more important to larger picture in any case. – Martijn Pieters Aug 21 '12 at 18:56
  • @Martin Pieters: Why is the use of dict as a key suspect in the first place? The usecase outlined in my comment above is a perfectly valid usecase in my view. Other programming languages (e.g., Perl) let you do this without any hassle. – Pat Aug 22 '12 at 11:19
  • @Pat: Sounds like you want to create a Vector class instead (with `__hash__()` and `__eq__` methods). – Martijn Pieters Aug 22 '12 at 11:21
1

Dictionaries can only use hashable objects as keys, which means they must be immutable. The default dictionary isn't either, so that won't work. You can try a frozendict though.

Community
  • 1
  • 1
orlp
  • 112,504
  • 36
  • 218
  • 315
1

Python wiki:

To be used as a dictionary key, an object must support the hash function (e.g. through __hash__), equality comparison (e.g. through __eq__ or __cmp__), and must satisfy the correctness condition above.

So trying this out:

a = {0: 0}
hash(a)

yields the error:

Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    hash(a)
TypeError: unhashable type: 'dict'

basically just confirming what mgilson already said. You are out of luck as far as using a dictionary (or a list, etc) as a dictionary key.

chucksmash
  • 5,777
  • 1
  • 32
  • 41
1

a dict can't be used as a key as it is unhashable. 

hash(a)

so i would rethink your problem or if you really need to hash a dict you could represent is a a string , or tuples and hash by that:

hash(tuple(dict.items()))
hash(''.join(["%s%s" %(k, v) for k,v in dict.items()]))
jassinm
  • 7,323
  • 3
  • 33
  • 42
  • While both problems can be worked around, as written: (1) `dict.items()` isn't hashable either, and (2) that string will give the same results for {1:23} as for {12:3}.. – DSM Aug 21 '12 at 18:56
  • I think you want `tuple(dict.items())`. – mgilson Aug 21 '12 at 19:03
0

Thanks to all who replied. I know this was a fairly basic question and all the infos on hashability and mutability is much appreciated.

I will indeed pursue the approach of mapping an input vector (a dictionary itself) to the sorted tuple of its items. This characterises a given dictionary unambiguously and is a hashable data structure such that it can be used as a dictionary key.

def get_key( dict1, dict2 ):

    list = dict1.items() + dict2.items()
    list.sort()
    return tuple( list )

a,b = {'feature1':0}, {'feature1':1}
print get_key( a, b )
Pat
  • 353
  • 1
  • 4
  • 15