Order of tuples in dict.items()

[Steven D'Aprano]

On Sun, 14 Oct 2007 13:26:27 -0700, Erik Max Francis wrote:

> Will McGugan wrote:
> 
>> If I have two dictionaries containing identical values, can I be sure
>> that the items() method will return tuples in the same order?
[...]
>> Can I rely on this behavior?
> 
> Probably not.

Definitely not. See Paul Hankin's earlier post in this thread.


> Dictionaries do not have an ordering that you should
> count on.  In practice, the order in which you get the items if you
> iterate over a dictionary is dependent on the hashing function, which
> can potentially change over time.

Well, I suppose it *is* possible for Python to change its hash function 
in some future version, but Python hashing is highly optimized, very fast 
and not likely to change.

It's especially not likely to change in the middle of a run of your 
program, say between calling a.items() and calling b.items().

However, the very nature of hash tables is that they are dependent on the 
order that items are added and removed; Python dicts are hash tables, and 
sure enough, their order is dependent on the order that items are added 
and removed. Here's the simplest example I could come up with:

>>> {-1: 'a', -2: 'b'}
{-2: 'b', -1: 'a'}
>>> {-2: 'b', -1: 'a'}
{-1: 'a', -2: 'b'}



> This is a case where most implementations _probably_ will return
> identical dictionaries in the same order when iterated over (of course,
> different implementations will have different orderings, but you don't
> care about that), but I wouldn't take the chance and rely on such an
> implementation detail.

I think this is a case of being right for the wrong reasons.


> If you want to keep track of the order in which objects were added to a
> dictionary, you'll need to keep a separate list of (sorted) keys, which
> is easy enough.

Keeping a list of keys *in the order they are added* is not the same as 
keeping a list of keys *sorted*. Here's an obvious example:

D = {}
D['b'] = 2
D['a'] = 1
D['c'] = 3

Insertion order: bac
Sorted order: abc


> If you're lazy there are plenty of recipes around for
> things like `SortedDictionary` or `sorteddict`.

I've never seen the point of a sorted dictionary, it's easy to just say:

for key, value in sorted(D.items())

An OrderedDict, that remembers the order that items are added, might be a 
good addition to the standard library. But that would depend on folks 
agreeing on its semantics.



-- 
Steven.