29

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

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

shahjapan
  • 12,609
  • 22
  • 69
  • 100

5 Answers5

44

Short answer: because they are mutable containers.

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

Ben James
  • 114,847
  • 26
  • 189
  • 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
18

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
  • 611
  • 6
  • 15
user240515
  • 2,796
  • 1
  • 26
  • 32
  • 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. – OrangeSherbet 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
  • 24,472
  • 5
  • 64
  • 80
  • and then can I replace normal dict bye dict = hashabledict – shahjapan Dec 24 '09 at 14:09
  • 8
    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