Why Python Dictionaries Became Ordered After Python 3.6: Underlying Implementation Details

The essence of a dictionary is a hash table, which finds a value via its key in average O(1) time. Whether a dictionary is ordered does not mean it can be sorted by key or value, but whether it can output key‑value pairs in the order they were inserted.

For an unordered dictionary, the insertion order and traversal order are not the same:

>> my_dict = dict()
>>> my_dict["name"] = "lowman"
>>> my_dict["age"] = 26
>>> my_dict["girl"] = "Tailand"
>>> my_dict["money"] = 80
>>> my_dict["hourse"] = None
>>> for key, value in my_dict.items():
...     print(key, value)
...
money 80
girl Tailand
age 26
hourse None
name lowman

The output of an ordered dictionary looks like this:

name lowman
age 26
girl Tailand
money 80
hourse None

Why did Python dictionaries become ordered after Python 3.6?

Before Python 3.6, the data structure looked like the following:

Because different keys have different hash values, the order of entries in the hash table is sorted by hash value, so traversal does not follow insertion order, appearing unordered.

This approach also wastes memory when the hash table is sparse. After Python 3.6, the implementation was optimized: the hash index and the actual key‑value pairs are stored separately, as shown:

‘indices’ points to a list of indexes, and ‘entries’ points to the original hash‑table storage structure.

You can think of ‘indices’ as a simplified hash table, and ‘entries’ as an array where each element stores the original hash result: the key and the value.

When looking up or inserting an element, the hash of the key modulo the length of ‘indices’ gives the array index, then the corresponding entry yields the result. For example, hash("key2") % 8 = 3, so indices[3] = 1, and entries[1] is the desired result:

This improves space utilization dramatically. On a 64‑bit OS, each pointer is 8 bytes, so the original layout required 8 × 3 × 8 = 192 bytes.

Now it becomes 8 × 3 × 3 + 1 × 8 = 80 bytes, saving about 58 % of memory, as shown:

Moreover, because ‘entries’ are inserted in order, iterating over the dictionary follows the insertion order, which is why dictionaries are ordered after Python 3.6.

If you are interested in the Python interpreter implementation, you can read the CPython source code; there are no secrets, and reading source is the fastest way to improve.