Dictionaries are ordered in Python 3.6
<p>Dictionaries are ordered in Python 3.6, unlike in previous Python incarnations. This seems like a substantial change, but it's only a short paragraph in the <a href="https://docs.python.org/3.6/whatsnew/3.6.html#other-language-changes">documentation</a>. It is described as an implementation detail rather than a language feature, but also implies this may become standard in the future.</p>

<p>How does the Python 3.6 dictionary implementation perform better than the older one while preserving element order? </p>

<p>Here is the text from the documentation:</p>

<blockquote>
  <p><code>dict()</code> now uses a âcompactâ representation <a href="https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html">pioneered by PyPy</a>. The memory usage of the new dict() is between 20% and 25% smaller compared to Python 3.5. <a href="https://www.python.org/dev/peps/pep-0468">PEP 468</a> (Preserving the order of **kwargs in a function.) is implemented by this. The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon (this may change in the future, but it is desired to have this new dict implementation in the language for a few releases before changing the language spec to mandate order-preserving semantics for all current and future Python implementations; this also helps preserve backwards-compatibility with older versions of the language where random iteration order is still in effect, e.g. Python 3.5). (Contributed by INADA Naoki in <a href="https://bugs.python.org/issue27350">issue 27350</a>. Idea <a href="https://mail.python.org/pipermail/python-dev/2012-December/123028.html">originally suggested by Raymond Hettinger</a>.)</p>
</blockquote>

<blockquote>
  <p>How does the Python 3.6 dictionary implementation perform better than the older one while preserving element order?</p>
</blockquote>

<p>Essentially by keeping two arrays, one holding the entries for the dictionary in the order that they were inserted and the other holding a list of indices.</p>

<p>In the previous implementation a sparse array of type <em>dictionary entries</em> had to be allocated; unfortunately, it also resulted in a lot of empty space since that array was not allowed to be more than <code>2/3</code>s full. This is not the case now since only the <em>required</em> entries are stored and a sparse array of type <em>integer</em> <code>2/3</code>s full is kept. </p>

<p>Obviously creating a sparse array of type "dictionary entries" is much more memory demanding than a sparse array for storing ints (<a href="https://github.com/python/cpython/blob/master/Objects/dict-common.h#L55">sized <code>8 bytes</code> tops</a> in cases of really large dictionaries) </p>

<hr>

<p><a href="https://mail.python.org/pipermail/python-dev/2012-December/123028.html">In the original proposal made by Raymond Hettinger</a>, a visualization of the data structures used can be seen which captures the gist of the idea.</p>

<blockquote>
  <p>For example, the dictionary:</p>

<pre><code>d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
</code></pre>
  
  <p>is currently stored as:</p>

<pre><code>entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]
</code></pre>
  
  <p>Instead, the data should be organized as follows:</p>

<pre><code>indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]
</code></pre>
</blockquote>

<p>As you can visually now see, in the original proposal, a lot of space is essentially empty to reduce collisions and make look-ups faster. With the new approach, you reduce the memory required by moving the sparseness where it's really required, in the indices.</p>

<hr>

<blockquote>
  <p>Should you depend on it and/or use it?</p>
</blockquote>

<p>As noted in the documentation, this is considered an implementation detail meaning it is subject to change and you shouldn't depend on it. </p>

<p>Different implementations of Python aren't required to make the dictionary ordered, rather, just support an ordered mapping where that is required (Notable examples are <em><a href="https://docs.python.org/3.6/whatsnew/3.6.html#pep-520-preserving-class-attribute-definition-order">PEP 520: Preserving Class Attribute Definition Order</a></em> and <em><a href="https://docs.python.org/3.6/whatsnew/3.6.html#pep-468-preserving-keyword-argument-order">PEP 468: Preserving Keyword Argument Order</a></em>)</p>

<p>If you want to write code that preserves the ordering and want it to not break on previous versions/different implementations you should always use <code>OrderedDict</code>. Besides, <code>OrderedDict</code> will most likely eventually become a thin-wrapper around the new <code>dict</code> implementation.</p>

python python-3.x dictionary python-internals python-3.6