Is it safe to use frozen set as Dict key?

Question

It obviously works but are there cases where two sets of same elements happen to add two entries in Dict? I guess I got this condition earlier and changed my code from frozenset(...) to tuple(sorted(frozenset(...))). Can someone who knows how Dict and frozenset implementation confirm if that is required or not?

Skeet

That's what it's intended for. If you have an example that causes issues, please post it. – Orthodontia

Answer 1

are there cases where two sets of same elements happen to add two entries in Dict?

No. frozenset hashing algorithm doesn't depend on the order of the elements, only on elements themselves. Two FS'es with the same elements are equal and have equal hashes, thus satisfying both criteria for "dict identity", in other words, they are the same dict key:

>>> a = frozenset([1,1,1,1,2,3])
>>> b = frozenset([3,3,3,3,2,1])
>>> {a:1, b:2}
{frozenset([1, 2, 3]): 2}

Tripartition

Answer 2

Is it safe to use a frozenset as a dict key? Yes.

According to the docs, Frozenset is hashable because it's immutable. This would imply that it can be used as the key to a dict, because the prerequisite for a key is that it is hashable.

From the FrozenSet docs

The frozenset type is immutable and hashable — its contents cannot be altered after it is created; it can therefore be used as a dictionary key or as an element of another set.

And redundantly, from the Dictionary docs:

...keys, which can be any immutable type

---

To clarify, a set (by definition), frozen or not, does not preserve order. They are stored internally with order not taken into account and with duplicate elements removed, so two sets built in different orders would be equivalent keys in a dictionary – they are the same.

>>> frozenset([1,2,2,3,3]) == frozenset([3,2,1,1,1])
True

and likewise,

>>> d = {}
>>> d[frozenset([1,1,2,3])] = 'hello'
>>> d[frozenset([1,2,3,3])]
'hello'
>>> d[frozenset([3,3,3,2,1,1,1])]
'hello'
>>> d[frozenset([2,1,3])]
'hello'

Thom

But the question was whether Frozensets built in different order, but with the same final values, have different hash values. The answer is no, they do not have different hash values. – Causality

I assumed this was understood because a set, by definition, does not preserve order. – Thom

You answered yes, meaning you think that the hashes can be different so tuple(sorted(frozenset(...))) is necessary. Its not a question of hashability or order, its a question of the hash value. – Causality

Answer 3

from the official docs

The frozenset type is immutable and hashable — its contents cannot be altered after it is created; it can therefore be used as a dictionary key or as an element of another set.

(Emphasis is mine)

Willis