Modern Dictionaries by Raymond Hettinger

[this video] Modern Dictionaries by Raymond Hettinger The official description of this talk is below, but personally, I'd watch any video with "Raymond Hettinger" in the title. > Python's dictionaries are stunningly good. Over the years, many great ideas have combined together to produce the modern implementation in Python 3.6. This fun talk is given by Raymond Hettinger, the Python core developer responsible for the set implementation and who designed the compact-and-ordered dict implemented in CPython for Python 3.6 and in PyPy for Python 2.7. He will use pictures and little bits of pure python code to explain all of the key ideas and how they evolved over time. He will also include newer features such as key-sharing, compaction, and versioning. This talk is important because it is the only public discussion of the state of the art as of Python 3.6. Even experienced Python users are unlikely to know the most recent innovations.

This implementation was used from 3.6, right? It's interesting that the idea mail mentions that nothing changes about the implementation (including order) but the memory layout. Which would imply insertion order was already preserved in older versions (not the case IIRC) or the idea underwent a few more changes that did in fact impact order. EDIT: I couldn't quite find an answer but [link] mentions the behavior happens since then because the implementation only tracks indices in the hash table itself and relies on maintaining entries separately in a second array that gets expanded in insertion order. This would also seem straightforward but it raises a few questions such as how deletion is implemented (efficiently). EDIT2: Okay, the talk ( [this video] ) mentions they just leave holes until the next resize (at around 42:00). Raymond also mentions there that his original idea didn't preserve ordering but happened due to an additional compacting optimization? Should probably watch the whole thing some time to get the history. Sounds like a fun talk.