How Ordered Dictionaries Work
The change to make dictionaries ordered involved improvements to the underlying implementation of the dictionary data structure. These improvements were aimed at both increasing the speed of dictionaries and reducing their memory footprint. As a fortunate side effect, these changes made it possible to maintain insertion order without significant performance penalties.
The CPython implementation of dictionaries uses a sparse table that contains indices into another, dense table holding the actual order of keys and values. When a new item is inserted, it goes into the next available slot in the dense table, thus preserving order. When items are deleted, the algorithm maintains the order of the remaining items, ensuring that the order reflects the sequence of insertion and deletion.
Are Python Dictionaries Ordered?
Yes, as of Python 3.7, dictionaries are ordered.
This means that when you iterate over a dictionary, insert items, or view the contents of a dictionary, the elements will be returned in the order in which they were added. This behavior was initially an implementation detail in Python 3.6 (in the CPython implementation) but was made a language feature in Python 3.7, ensuring that all implementations of Python must maintain this order.
This is a significant change from Python 3.5 and earlier, where dictionaries were unordered, and you could not rely on the order of items in a dictionary. For scenarios where order mattered in these older versions, you had to use collections like OrderedDict from the collections module. However, with the ordered nature of dictionaries from Python 3.7 onwards, the need for OrderedDict has diminished for most use cases, though it still retains some specific functionalities that differentiate it from regular dictionaries.