Python dict key ordering

Due to dicts preserving the order of key insertion, they’re another example of objects that may have == True but with other methods yielding different values:

>>> x = dict(a=1, b=2)
>>> y = dict(b=2, a=1)
>>> x == y
True
>>> list(x)
['a', 'b']
>>> list(y)
['b', 'a']

How does Python implement remembering key insertion order? Raymond Hettinger’s 2017 talk Modern Python Dictionaries A confluence of a dozen great ideas talks about how the ordering is a side effect of other optimizations. Slides.

PEP 468 – Preserving the order of **kwargs in a function (2014) points to the message where Hettinger proposed compact dicts: [Python-Dev] More compact dictionaries with faster iteration. The ActiveState link therein is dead but archive.org has a copy: https://web.archive.org/web/20190217120809/http://code.activestate.com/recipes/578375/

From that working Python prototype, we can see the order getting preserved here:

    def __setitem__(self, key, value):
        hashvalue = hash(key)
        index, i = self._lookup(key, hashvalue)
        if index < 0:
            self.indices[i] = self.used
            self.hashlist.append(hashvalue)
            self.keylist.append(key)
...

I’ll plan to take a look at how that actually got implemented in CPython sometime soon, inspired by a 2011 post from Hettinger: Open Source Challenge: Open Your Source, More.