Do dicts preserve iteration order if they are not

问题:

If I have a dictionary in Python, and I iterate through it once, and then again later, is the iteration order guaranteed to be preserved given that I didn't insert, delete, or update any items in the dictionary? (But I might have done look-ups).

回答1:

Here is what dict.items() documentation says:

dict.items() return a copy of the dictionary’s list of (key, value) pairs.

If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called with no intervening modifications to the dictionary, the lists will directly correspond.

I think it's reasonable to assume that item ordering won't change if all you do is iteration.

回答2:

The standard Python dict like most implementations does not preserve ordering as the items are usually accessed using the key.

However predictable iteration is sometime useful and in Python 3.1 the collections module contains an OrderedDict that is order preserving with minimal performance overhead.

回答3:

Yes. There's no randomisation involved. There's an even stronger guarantee -- see here.

回答4:

collections.OrderedDict will be available in Python 2.7 in addition to Python 3.1.

For Python versions earlier than 2.7, there's collective.ordereddict on PyPI, and Django has its own SortedDict implementation.

回答5:

A Python dictionary has no concept of order. So you can't depend on a specific order while iterating.

This is deliberate: since it's a hashmap it's unavoidable if you want 'fast lookups'!

回答6:

It might be preserved in some implementations, but don't count on it, as it is not a part of the Dict spec.

回答7:

As Christophe said, a dictionary is used to organise key/value pairs because of the fast access time it provides. If you application needs a fixed index, you should look at the other data structures that provide a specific/known order.

Having said that, it should be safe to assume that the order doesn't change unless items are added (there wouldn't be any point to do this expensive operation of reshuffling stuff) etc but, again, don't rely on it.