Equivalence of dictionary keys?

[Blair Hall]

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?

[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.

[Duncan Booth]

Blair Hall <b.****@irl.cri.nz> wrote in news:3F**************@irl.cri.nz:

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?

Here's a simple counter-example using not two but one dictionary. Just
manipulating a dictionary can change the order of the keys:

d = {'a':1, 'b': 2, 'c': 3}
d.keys() ['a', 'c', 'b'] for i in range(100): d[i] = i

for i in range(100): del d[i]

d.keys() ['c', 'b', 'a']

However, the answer to your original question is NO, you don't have to sort
the keys to find out whether the two dictionaries are the same. You could
just iterate over one set of keys and check for membership of the other
set.

def samekeys(d1, d2):
if len(d1) != len(d2):
return False
for k in d1:
if not k in d2:
return False
return True

dict1 = {'a':1, 'b': 2, 'c': 3}
dict2 = dict1.copy()
for i in range(100):
dict1[i] = i
for i in range(100):
del dict1[i]

print dict1.keys()
print dict2.keys()
print samekeys(dict1, dict2)

--
Duncan Booth du****@rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?

[Emile van Sebille]

Duncan Booth:

Blair Hall:

I am guessing that two dictionaries with the same keys
will sort them in the same order but is this true?
Here's a simple counter-example using not two but one dictionary.

Just manipulating a dictionary can change the order of the keys:

Borrowing your jumble keys example, you can also use sets

d = {'a':1, 'b': 2, 'c': 3}
c = {'a':1, 'b': 2, 'c': 3}
for i in range(100): d[i] = i

for i in range(100): del d[i]

a = d.keys()
b = c.keys()

import sets
print sets.Set(a) == sets.Set(b)

--

Emile van Sebille
em***@fenx.com