Using a Python Dictionary as a Key (Non-nested)
Solution 1
If you have a really immutable dictionary (although it isn't clear to me why you don't just use a list of pairs: e.g. [('content-type', 'text/plain'), ('host', 'example.com')]
), then you may convert your dict
into:
-
A tuple of pairs. You've already done that in your question. A
tuple
is required instead oflist
because the results rely on the ordering and the immutability of the elements.>>> tuple(sorted(a.items()))
-
A frozen set. It is a more suitable approach from the mathematical point of view, as it requires only the equality relation on the elements of your immutable
dict
, while the first approach requires the ordering relation besides equality.>>> frozenset(a.items())
Solution 2
If I needed to use dictionaries as keys, I would flatten the dictionary into a tuple of tuples.
You might find this SO question useful: What is the best way to implement nested dictionaries?
And here is an example of a flatten module that will flatten dictionaries: http://yawpycrypto.sourceforge.net/html/public/Flatten.Flatten-module.html
I don't fully understand your use case and I suspect that you are trying to prematurely optimize something that doesn't need optimization.
Solution 3
To turn a someDictionary into a key, do this
key = tuple(sorted(someDictionary .items())
You can easily reverse this with dict( key )
Solution 4
One way to do this would be to subclass the dict and provide a hash method. ie:
class HashableDict(dict):
def __hash__(self):
return hash(tuple(sorted(self.iteritems())))
>>> d = HashableDict(a=1, b=2)
>>> d2 = { d : "foo"}
>>> d2[HashableDict(a=1, b=2)]
"foo"
However, bear in mind the reasons why dicts (or any mutable types) don't do this: mutating the object after it has been added to a hashtable will change the hash, which means the dict will now have it in the wrong bucket, and so incorrect results will be returned.
If you go this route, either be very sure that dicts will never change after they have been put in the other dictionary, or actively prevent them (eg. check that the hash never changes after the first call to __hash__
, and throw an exception if not.)
Solution 5
Hmm, isn't your use case just memoizing function calls? Using a decorator, you will have easy support for arbitrary functions. And yes, they often pickle the arguments, and using circular reasoning, this works for non-standard types as long as they can be pickled.
See e.g. this memoization sample
Casebash
Bachelor of Science (Adv Maths) with Honors in Computer Science from University of Sydney Programming C/C++/Java/Python/Objective C/C#/Javascript/PHP
Updated on February 16, 2020Comments
-
Casebash about 4 years
Python doesn't allow dictionaries to be used as keys in other dictionaries. Is there a workaround for using non-nested dictionaries as keys?
The general problem with more complicated non-hashable objects and my specific use case has been moved here. My original description of my use case was incorrect.
-
mmmmmm over 14 yearsI think repl(a) would be better here as str might not be unique
-
Casebash over 14 yearsThis solves nesting, but does it do if the values are non-standard types? Does it pickle the values as well?
-
Andrey Vlasovskikh over 14 years
repr
of the different objects might not be different. The "difference" among Python objects is usually coded as__eq__
, not__repr__
. -
Brian over 14 years
repr
andstr
are actually the same for dicts anyway. However, you could run into trouble this way - it's possible to get dicts with different internal state so that, while they contain the same items, they list their keys in a different order, and would thus produce a different key. You'll also run into trouble if you store objects without the property thatrepr(x)==repr(y)
<=> x==y in the dict (eg. most user created classes). -
Andrey Vlasovskikh over 14 yearsIMO, serialization is an overhead here. And @Casebash made a good point by mentioning the problem with non-standard types.
-
user1066101 over 14 years+1:
tuple( someDictionary.items() )
works really, really well for making a dictionary into an immutable key. -
user1066101 over 14 years-1: Use
tuple( someDictionary.items() )
instead ofrepr
. it gives you a structure that can be trivially transformed back into a dictionary without resorting toeval
. -
Brian over 14 yearsMake that
tuple(sorted(somedictionary.items())
- the order of keys is not guaranteed, which means equal dicts might produce different reprs by listing the items in a different order. -
Ryu over 14 yearsOverriding all mutating methods to raise an error will catch mistakes earlier at the cost of more code.
-
Denis Otkidach over 14 yearsSorting in important. To see why you have to find 2 different key values with equal hash (it's probably hard to find for strings, but can be easily achieved with user defined objects), then construct 2 equal dictionaries by inserting them in different order. You'll get equal dictionaries with different order in
.items()
. -
Denis Otkidach over 14 yearsThis won't work when you get hash collision. See my comment to other answer to see how to demonstrate the problem.
-
Andrey Vlasovskikh over 14 years+1, though I find my solution with
frozenset
more "correct", see my answer. -
user1066101 over 14 years+1: Good point on ordering. A dictionary can always be transformed to a frozenset because the keys must be unique, assuring each tuple will be preserved in the set. Elegant.
-
Casebash over 14 yearsThis is a nice solution which is more general than than the specific problem I posed, but doesn't this doesn't handle dictionaries within dictionaries.
-
Casebash over 14 yearsThe difficulty with this is that each dictionary has to be sorted
-
Casebash over 14 yearsAgain, this is a solution to the more specific problem, but the more general problem is open
-
Casebash over 14 yearsNow moved this to a new question
-
AnukuL over 6 yearsNote that, Frozen set solution will not work, if the dict contains list or any other mutable object as values. For ex: a={'key1': 'val1', 'key2': ['val2', 'val3']}
-
BallpointBen over 5 years
tuple(sorted())
will work as long as the dict's keys are comparable.frozenset
requires hashable dict values.