1

If I make two dictionaries with the same keys, it seems like they return values in the same order, even though dictionaries aren't ordered. For instance, if I do this:

dict1 = {"a":1, "b":2, "c":3, "d":4}
dict2 = {"a":10, "b":20, "c":30, "d":40}

zip(dict1.values(), dict2.values())

It gives the "desired" output:

[(1, 10), (3, 30), (2, 20), (4, 40)]

Why does this happen? Can I always count on two dictionaries with the same keys having their values ordered in the same way?

C_Z_
  • 7,427
  • 5
  • 44
  • 81
  • 1
    It's not that they aren't ordered, it's just that the order is arbitrary and can depend on which version of python you're using. I wouldn't do it. – NightShadeQueen Jul 17 '15 at 15:55
  • 1
    They aren't _guaranteed_ to be ordered. An implementation of Python _might_ order them, but because it's not guaranteed (i.e., it is not in the specifications for implementations of Python), it is not something you should rely on in your code. – Jake Griffin Jul 17 '15 at 15:59

1 Answers1

4

Keys are often in the same order, but there is no guarantee. If there are no hash value collisions then the keys will be in order. But there can be collisions, and in that case the order of insertion will affect the order of the keys.

For example, 1 and 65 generate hash collisions due to dictionaries having sizes that are powers of two (on my machine, at least). 1 % 8 == 65 % 8, so the two keys map to the same hash table bucket.

>>> {1: 'foo', 65: 'bar'}
{1: 'foo', 65: 'bar'}
>>> {65: 'bar', 1: 'foo'}
{65: 'bar', 1: 'foo'}

Identical dictionaries but different insertion order means the keys are ordered differently.

>>> {1: 'foo', 65: 'bar'} == {65: 'bar', 1: 'foo'}
True

This is just an example that happens to (not) work on my Python version. Python the language does not specify how keys map to hash buckets.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
  • Note though, that not all implementations of Python will necessarily even have a collision on 1 and 65. It is not in the specifications of Python how the hashing should work (just that they should be hashed for efficient lookup), so the collisions can be different based on the particular implementation. +1 for finding an example though! – Jake Griffin Jul 17 '15 at 16:02
  • Thanks for the very helpful answer. If I may ask a follow-up question; if both dictionaries are always created with the keys in the same insertion order, can I count on there not being any hash value collisions? I'm not going to use this method either way because it seems unreliable, but now I'm curious. – C_Z_ Jul 17 '15 at 16:06
  • 1
    As a rule, I would not write any code that depends on insertion order. But if you're just asking out of curiosity then yes, if you use the same keys with the same insertion order you can expect them to be in the same order. I would not depend on that behavior, but I'd be surprised if there were a Python implementation that behaved differently. – John Kugelman Jul 17 '15 at 16:20