Do Python 3.6 Dictionaries Maintain Insertion Order and How Is This Implemented?

Are Dictionaries Ordered in Python 3.6 ?

In Python versions 3.6 and later, dictionaries exhibit insertion order, meaning they retain the order in which key-value pairs are added. This behavior is not guaranteed across all Python implementations, and solely applies to the CPython interpreter.

Improved Efficiency of Python 3.6 Dictionary Implementation

The new dictionary implementation in Python 3.6 utilizes two arrays to maintain both insertion order and efficient hash lookups.

• dk_entries: Contains entries (key-value pairs) in the order of insertion.
• dk_indices: Stores indices corresponding to each entry in dk_entries, acting as a hash table.

This approach leverages the smaller size of integer arrays (dk_indices) compared to the previously used sparse array of key-value entries (dk_entries), resulting in a more compact memory footprint. The sparse array previously allocated to accommodate a fixed size 2/3 empty spaces for performance optimization is no longer necessary.

Visualization of Data Structures

An example dictionary:

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

Old Data Structure:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

New Data Structure:

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

As illustrated, the new structure separates indices and entries, enabling a more efficient memory allocation and faster hash table lookup due to the smaller size of the indices array.

Conclusion

The enhanced dictionary implementation in Python 3.6 effectively maintains insertion order while optimizing memory usage through the use of separate entry and index arrays. This optimization results in a more efficient representation and management of dictionaries, particularly in scenarios with memory constraints or when large dictionaries are processed.

The above is the detailed content of Do Python 3.6 Dictionaries Maintain Insertion Order and How Is This Implemented?. For more information, please follow other related articles on the PHP Chinese website!