Are Python Dictionaries Guaranteed to Maintain Insertion Order in 3.6 ?

Are Dictionaries Ordered in Python 3.6 ?

As of Python 3.6, dictionaries in the CPython implementation are insertion ordered, meaning they preserve the order of items inserted. However, this behavior is considered an implementation detail and should not be relied upon.

Guaranteed Insertion Order in Python 3.7

In Python 3.7, insertion ordering for dictionaries became a guaranteed language feature. This means that all conforming Python implementations must offer an insertion ordered dictionary.

Performance Improvements with Insertion Ordering

The new dictionary implementation in Python 3.6 achieves insertion ordering by maintaining two arrays:

• dk_entries: Holds key and value entries in the order of insertion.
• dk_indices: Stores indices into dk_entries, acting as a hash table.

This design reduces memory overhead by storing only the required entries and using a sparse array of indices. The previous implementation allocated a sparse array of key and value entries, resulting in empty spaces.

Data Structure Visualization

For example, the dictionary { 'timmy': 'red', 'barry': 'green', 'guido': 'blue' } is stored as:

indices = [None, 1, None, None, None, 0, None, 2]
entries = [[-9092791511155847987, 'timmy', 'red'],
           [-8522787127447073495, 'barry', 'green'],
           [-6480567542315338377, 'guido', 'blue']]

In the old design, there would be numerous empty spaces to minimize collisions. The new approach reduces memory usage by moving the sparseness to the indices array.

In conclusion, the insertion ordering in Python 3.6 dictionaries is a significant improvement that enhances memory efficiency and makes dictionaries more reliable across Python implementations.

The above is the detailed content of Are Python Dictionaries Guaranteed to Maintain Insertion Order in 3.6 ?. For more information, please follow other related articles on the PHP Chinese website!