On Thu, Apr 3, 2014 at 4:24 PM, Chris Angelico
On Fri, Apr 4, 2014 at 6:14 AM,
wrote: Iterating in insertion order would make the iteration completely independent of the hashing algorithm. The hashing algorithm determines what buckets each item goes in, but you don't _have_ to iterate in bucket order, depending on your data structure. C#, for example, stores items in an array [which are populated from a freelist of array slots that don't have items in them, or sequentially at the end of the array if there are no slots in the freelist] and the buckets as linked lists within the array.
However that's done, it implies additional storage beyond the straight-forward mapping, right? Python's dict implementation is *highly* optimized (which is necessary, given how much of Python is built on dicts), and any proposal that basically says "Every dict needs to keep track of insertion order, for the sake of the handful of cases where you actually care" is likely to have the aerodynamic qualities of a rock.
Raymond has a proposal (back-burnered?) for a compact dict implementation that preserves order in iteration until the first deletion: https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2013-May/126327.html -eric