Equivalence of dictionary keys?

[Andrew Bennetts]

On Tue, Dec 02, 2003 at 04:22:52PM +1300, Blair Hall wrote:
> I would like to determine whether two dictionaries have the
> same set of keys. Can anyone tell me if I HAVE to sort
> the key sequences as in this code snippet:
> 
>    # d1, d2 already created
>    k1 = d1.keys()
>    k1.sort()
>    k2 = d2.keys()
>    k2.sort()
> 
>    # are the keys the same?
>    same = (k1 == k2)
> 
> I am guessing that two dictionaries with the same keys
> will sort them in the same order but is this true?

Not necessarily.  There's at least one case where this isn't true: in the
case of hash collisions between keys inserted in different orders in the two
dictionaries, e.g.:

>>> class C:
...     def __hash__(self):
...         return 1
... 
>>> c1, c2 = C(), C()
>>> d1, d2 = {}, {}
>>> d1[c1] = 'a'
>>> d1[c2] = 'b'
>>> d2[c2] = 'b'
>>> d2[c1] = 'a'
>>> d1.keys()
[<__main__.C instance at 0x4021b7ec>, <__main__.C instance at 0x4021b5ec>]
>>> d2.keys()
[<__main__.C instance at 0x4021b5ec>, <__main__.C instance at 0x4021b7ec>]
>>> 

In pathological cases, even sorting the keys isn't enough:

>>> class C:
...     def __hash__(self):
...         return 1
...     def __eq__(self, other):
...         return 0
...     def __lt__(self, other):
...         return 1
... 
>>> c1, c2 = C(), C()
>>> d1, d2 = {}, {}
>>> d1[c1] = 'a'
>>> d1[c2] = 'b'
>>> d2[c2] = 'b'
>>> d2[c1] = 'a'
>>> k1 = d1.keys()
>>> k2 = d2.keys()
>>> k1
[<__main__.C instance at 0x4021b54c>, <__main__.C instance at 0x4021b5cc>]
>>> k2
[<__main__.C instance at 0x4021b5cc>, <__main__.C instance at 0x4021b54c>]
>>> k1.sort()
>>> k2.sort()
>>> k1 == k2
False
>>> k1
[<__main__.C instance at 0x4021b5cc>, <__main__.C instance at 0x4021b54c>]
>>> k2
[<__main__.C instance at 0x4021b54c>, <__main__.C instance at 0x4021b5cc>]
>>> 

-Andrew.