31

I mean why cant we put key of dict as dict?

that means we can't have dictionary having key as another dictionary...

shahjapan
  • 13,637
  • 22
  • 74
  • 104

6 Answers6

46

Short answer: because they are mutable containers.

If a dict was hashed, its hash would change as you changed its contents.

Ben James
  • 121,135
  • 26
  • 193
  • 155
  • 2
    I don't even want to begin to imagine the nightmarish logic it would take to use an object as the key. – David Dec 24 '09 at 08:40
  • 8
    Actually Python makes hashing objects easy, it gives each one a unique and constant identity which can be hashed. – Ben James Dec 24 '09 at 08:42
  • yes, but by default instances of user defined objects always compare unequal. –  Dec 24 '09 at 08:47
  • but I wonder what's the reason behind it - to keem dict. unhashable? – shahjapan Dec 24 '09 at 08:51
  • 6
    make a hashable representation of the dict if you must -- for example `frozenset(D.items())` (for `D` dict). A `frozenset` is a hashable and immutable set -- a `set` is unhashable for the same reason as `dict`. – u0b34a0f6ae Dec 24 '09 at 10:37
  • @shahjapan: the reason is that it prevents hard-to-find bugs, especially for people that don't understand hashing all that well. As Dave Kirby shows below, there is a simple workaround, but that you have to use a workaround is a simple warning that you need to understand what you are doing, lest you 'lose' key-value pairs. – Confusion Dec 24 '09 at 13:07
  • @Confusion yes thanks I understood now, but I was Wondering because if you consider java or c# Hashtables are hashable by default :-) – shahjapan Dec 24 '09 at 14:10
  • @kaizer.se: for frozenset to freeze a dictionary, all the dictionary keys and values need to be hashable too. try `frozenset({1:2, 3:[]})`. – tzot Dec 25 '09 at 09:37
  • One can easily implement `__hash__` for a `dict` kind of `object` - which won't be changed even `dict` items change, as we are keeping whole `dict` as `Key` not `the key of a dict` as `Key`. – shahjapan Jun 24 '12 at 07:58
  • 1
    This answer is contradicted by one of the rationales for not having a frozendict - http://legacy.python.org/dev/peps/pep-0416/ - that users can "can agree by convention" not to mutate a shared dict, so there's "no great need" to worry about this problem. – Chris Martin May 20 '14 at 00:24
20

This is easy to deal with. Wrap a dict in a frozenset before you hash it. Then, when you need to use it, convert it back to a dict.

>>> unhashable = {'b': 'a', 'a': 'b'}
>>> hashable = frozenset(unhashable.items())
>>> unhashable = dict(hashable)
>>> unhashable
{'a': 'b', 'b': 'a'}

Note that dictionary key order is undefined anyway, so the change in key order doesn't matter.

hso
  • 631
  • 6
  • 15
user240515
  • 3,056
  • 1
  • 27
  • 34
  • 3
    The hash of a frozen dictionary doesn't depend on the values, only the keys. Thus for those of you looking to use a dictionary as a key to another dictionary, this won't work, if that's what you're looking for. – JoseOrtiz3 Dec 13 '18 at 22:43
  • 1
    It would fail if any of the item contains another `dict` – nehem Feb 03 '19 at 23:55
5

As others have said, the hash value of a dict changes as the contents change.

However if you really need to use dicts as keys, you can subclass dict to make a hashable version.

>>> class hashabledict(dict):
...    def __hash__(self):
...        return id(self)
... 
>>> hd = hashabledict()
>>> d = dict()
>>> d[hd] = "foo"
>>> d
{{}: 'foo'}

>>> hd["hello"] = "world"
>>> d
{{'hello': 'world'}: 'foo'}

This replaces the hash value used for the dict with the object's address in memory.

Dave Kirby
  • 25,806
  • 5
  • 67
  • 84
  • and then can I replace normal dict bye dict = hashabledict – shahjapan Dec 24 '09 at 14:09
  • 9
    But this is useless: if I store a value under `{}`, I can't look it up with `{}`, because the two empty hashabledicts have different ids, and different hashes. The important thing about a hash function is that it must return the same hash for two "equal" values. – Ned Batchelder Dec 24 '09 at 15:04
  • 1
    @Ned - Doh! You are right. What is really needed is a frozendict that acts the same way as a frozenset. You could subclass dict to define one, as in this recipe on ASPN: http://code.activestate.com/recipes/414283/ – Dave Kirby Dec 24 '09 at 15:52
  • 2
    It could be useful if you simply want to distinguish between different dicts though. But beware; if one dict was garbage-collected, a newly instantiated dict could reside at the same place in memory, thus yielding the same `id()`, giving rise to a hard to find bug. – Brecht Machiels Nov 18 '13 at 21:31
1

None of the mutable container types in Python are hashable, because they are mutable and thus their hash value can change over their lifetime.

  • 4
    tuples and strings are containers, yet hashable and immutable. – Ignacio Vazquez-Abrams Dec 24 '09 at 08:40
  • 2
    @Ignacio Vazquez-Abrams: strings are sequences but not containers. Also, a tuple containing a non-hashable item is also non-hashable; try using `([1], {2:3})` as a dict key. – tzot Dec 25 '09 at 09:41
1

For maybe the wrong reasons I've ran into this problem a bunch of times; where I want to reference a full dict as a key to something. I don't need it to be mutable, but I do want to preserve and easily access the dict's members.

The easiest way I've found to make the dict immutable and quickly usable as a key value is to make it a JSON (or serialize in your favorite alternative).

For example:

>>> import json
>>> d = {'hey':1, 'there':2}
>>> d_key = json.dumps(d)
>>> d_key
'{"there": 2, "hey": 1}'
>>> d2 = {d_key: 'crazytown'}
>>> d2
{'{"there": 2, "hey": 1}': 'crazytown'}

It's easy to manipulate, since it's just a string. And, it can be de-serialized into an object if you want to reference its members.

Bill Gross
  • 496
  • 3
  • 11
  • This will fail if the dictionary is serialized in a different order. In dicts the order of elements does not matter, but when you create a string from it and compare it as such, two dicts with identical content may not match. – Martin Melka Jan 22 '18 at 12:34
  • 1
    @MartinMelka is it still true with Python 3.7 which has ordered dicts by defaylt? – Cedric H. Jan 08 '19 at 18:54
0

You can use id(inner_dict) as the key to the outer dictionary.

This gives the same behavior as Java where the default hashcode of an Object is guaranteed to be unique for that object (the memory address for practical purposes - but this is implementation specific) and is used as the hashcode for inserting into HashMap.

So in Java you can have a HashMap<HashMap<Integer, Integer>, Integer>

In Python some_dict = {{1: 1}: 1} will give you TypeError: unhashable type: 'dict'

alexkim
  • 36
  • 6