[Python] How do Python dictionaries do O(1) deletion on average while keeping insertion order

From the Python docs:

Changed in version 3.7: Dictionary order is guaranteed to be insertion order. This behavior was an implementation detail of CPython from 3.6.
​

Example:

my_dictionary = {
"name": "Alice",
"age": 30,
"city": "Wonderland",
"hobbies": ["reading", "adventuring", "tea parties"],
"is_active": True,
}

my_dictionary["r"] = "d"
del my_dictionary["age"]
del my_dictionary["is_active"]
my_dictionary["is_active"] = False

print(my_dictionary.keys())

>>> dict_keys(['name', 'city', 'hobbies', 'r', 'is_active'])


I'm curious as to how they achieve O(1) average complexity for a delete operation.

From what I understand, to maintain a dictionary that maintains elements in the same order that they were added, you need a combination of a hash table (for most dictionary operations) and an array (to keep order). That's actually how OrderedDictionary is implemented in C# (where the Remove operation is O(n)).

I looked at the CPython source code and it looks like there is a hash table and an array. I think that's the clever bit they did (although it only talks about popping the last item):

It's simple for combined table. Since dk_entries is mostly append only, we can get insertion order by just iterating dk_entries.

One exception is .popitem(). It removes last item in dk_entries and decrement dk_nentries to achieve amortized O(1). Since there are DKIX_DUMMY remains in dk_indices, we can't increment dk_usable even though dk_nentries is decremented.
​

Continue reading...