how reliable is python’s dictionary ordering?

ghz 13hours ago ⋅ 5 views

I need to quickly hash a dictionary (a counter), and I’m noticing that python seems to order dictionaries with the same keys in the same order, even if they are constructed differently. In fact the dictionaries seem to be able to survive quite a bit of abuse:

>>> D = {'a': 1, 'b': 2, 'c': 3}
>>> list(D)
['b', 'c', 'a']
>>> list(D)
['b', 'c', 'a']
>>> list(D)
['b', 'c', 'a']
>>> list(D)
['b', 'c', 'a']
>>> E = {'a': 1, 'b': 2, 'c': 3}
>>> list(E)
['b', 'c', 'a']
>>> list(E)
['b', 'c', 'a']
>>> list(E)
['b', 'c', 'a']
>>> F = {'a': 1, 'b': 2, 'c': 3}
>>> list(F)
['b', 'c', 'a']
>>> list(F)
['b', 'c', 'a']
>>> list(F)
['b', 'c', 'a']
>>> list(F)
['b', 'c', 'a']
>>> G = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
>>> list(G)
['b', 'c', 'a', 'd']
>>> list(G)
['b', 'c', 'a', 'd']
>>> list(G)
['b', 'c', 'a', 'd']
>>> list(F)
['b', 'c', 'a']
>>> F.pop('a')
1
>>> list(F)
['b', 'c']
>>> F['a'] = 2
>>> list(F)
['b', 'c', 'a']
>>> list(F)
['b', 'c', 'a']
>>> H = {'b': 2, 'a': 1, 'c': 3}
>>> list(H)
['b', 'c', 'a']
>>> H = {'b': 2, 'c': 1, 'a': 3}
>>> list(H)
['b', 'c', 'a']
>>> K = {'b': 2, 'c': 1, 'a': 3, 'd': 4}
>>> list(K)
['b', 'c', 'a', 'd']
>>> K = {'b': 2, 'c': 1, 'd': 3, 'a': 4}
>>> list(K)
['b', 'c', 'a', 'd']

My question is then, if my dictionaries have the same keys and the same values, can I count on the keys being in the same order, at least for the lifetime of that running instance of python? Note that I’m aware python is a bit incomprehensible in how it decides to order a dictionary, but I want to know if given the same inputs, the same instance of python will return the same key ordering each time.

Answer

Yes, in Python 3.7 and later, the order of keys in a dictionary is guaranteed to be insertion order. This means that once a dictionary is created, the keys will appear in the order they were added to the dictionary, even if you perform various operations like reordering or modifying it.

Key points to consider:

  1. Insertion Order: In Python 3.7+, dictionaries maintain the order in which items are inserted. This behavior is guaranteed by the language specification, which was introduced in Python 3.7. So, given that you are inserting keys in a particular order, that order will be preserved in the dictionary.

  2. Changing the Dictionary:

    • If you remove and add items, they will appear in the order they were added after the modification.
    • If you pop items or use del, the order of the remaining items will still be maintained as per their insertion sequence.
    • If you construct a new dictionary with the same keys and values, and the items are added in the same order, the dictionary will have the same order of keys.

  3. Same Dictionary Across Runs: However, Python dictionaries do not guarantee that the key order will be the same across different Python runs unless the dictionary is constructed in exactly the same way (with the same order of insertions). The ordering can be impacted by factors like:

    • The specific version of Python
    • The implementation (e.g., CPython vs. PyPy)
    • Internal optimizations or changes in the Python interpreter (though these are rare, they can influence the implementation details of certain data structures).

Your Specific Question:

For the lifetime of a single Python session, if you are using the same keys and values, you can rely on the keys being ordered in the same way each time you access the dictionary, provided the dictionary has been constructed in the same way. So for your example:

D = {'a': 1, 'b': 2, 'c': 3}
E = {'a': 1, 'b': 2, 'c': 3}
  • As long as D and E are created in the same way (with the same insertions in the same order), they will have the same key order.
  • Operations like pop, del, and update will not change the fact that the order of insertion is preserved, unless you manually modify the order of the dictionary after creation.

Practical Example:

D = {'a': 1, 'b': 2, 'c': 3}
print(list(D))  # Output: ['a', 'b', 'c']

D['d'] = 4
print(list(D))  # Output: ['a', 'b', 'c', 'd']

D.pop('a')
print(list(D))  # Output: ['b', 'c', 'd']

# Inserting 'a' back at the end
D['a'] = 1
print(list(D))  # Output: ['b', 'c', 'd', 'a']

Conclusion:

For a single Python session, you can safely rely on the dictionary maintaining its insertion order. However, across different runs or Python instances, the ordering is not guaranteed unless the dictionaries are created in the same manner.

This behavior is critical for hashing dictionaries as well — you cannot rely on key order when hashing unless the dictionary is exactly the same, which is why using dictionaries as keys in other dictionaries (or in sets) might lead to different results if order is altered.

#py