Equivalence of dictionary keys?

B

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?
 
A

Andrew Bennetts

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.:
.... 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()
d2.keys()

In pathological cases, even sorting the keys isn't enough:
.... 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
k1.sort()
k2.sort()
k1 == k2 False
k1

-Andrew.
 
D

Duncan Booth

Blair Hall said:
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

del d


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
for i in range(100):
del dict1

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

Emile van Sebille

Duncan Booth:
Blair Hall:

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

for i in range(100): del d

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

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top