frozendict (v0.1)

[Arnaud Delobelle]

kj <no.email at please.post> writes:

> Following a suggestion from MRAB, I attempted to implement a
> frozendict class.  My implementation took a lot more work than
> something this simple should take, and it still sucks.  So I'm
> hoping someone can show me a better way.  Specifically, I'm hoping
> that there is a "recipe" for building off standard classes that
> cover all the bases with a minimum of tedious repetitive work.
>
> Here's my little monster:
>
> class frozendict():
[...]
>     def __hash__(self):
>         return hash(tuple(self.items()))

There is a problem with this hash function stemming from the fact that
the hash value of a tuple is different depending on the order of its
elements, i.e. hash((1, 2)) is not equal to hash((2, 1)).

Now, if there is a hash collision in the keys of the dictionary, then
the order of enumeration of its items will depend on the order in which
they were inserted into the dictionary.  Here is a simple example below 

>>> h = hash('a') # So h and 'a' have the same hash value
>>> d = {'a':1, h:2}
>>> d1 = {'a':1, h:2}
>>> d2 = {h:2, 'a':1}
>>> d1 == d2 # The dictionaries are equal...
True
>>> tuple(d1.items()) # but their items are enumerated in...
(('a', 1), (-468864544, 2))
>>> tuple(d2.items()) # different orders!
((-468864544, 2), ('a', 1))

A simple fix is to use hash(frozenset(self.items())) instead.

-- 
Arnaud