Are sorted keys guaranteed by a Python dictionary?

Question

That iterating over a dict could yield sorted keys was surprising. It would be considerably useful too, if this is a guaranteed behaviour.

example code

fruits = {3: "banana",
          4: "grapes",
          1: "apple",
          2: "cherry"}

# Looping over the dict itelf
for each in fruits:
    print each, fruits[each]

output

1 apple
2 cherry
3 banana
4 grapes

# Looping over the generator produces the same result too
for each in iter(fruits):
    print each, fruits[each]

Note: I would like to point out that I don't want implement an ordered dict. I just wanted to verify if the code written above is a normal, recurring behavior in python (version 2.7 above)

Python dictionaries aren't sorted, regardless of how you output the values. There is some related information in the post [python dictionary sort by key](http://stackoverflow.com/questions/9001509/python-dictionary-sort-by-key) — Michelle Welcks, Feb 15 '14 at 06:41
possible duplicate of [How to make a sorted dictionary class?](http://stackoverflow.com/questions/21309374/how-to-make-a-sorted-dictionary-class) — thefourtheye, Feb 15 '14 at 06:44
@thefourtheye I saw that question before. But they are trying to implement a sorted dict. Here, I am asking if the afore mentioned code was a default behavior in Python. — , Feb 15 '14 at 07:07

score 3 · Accepted Answer · edited May 23 '17 at 12:20

3

You can subclass the dict and create your own SortedDict class, like this

class SortedDict(dict):
    def __iter__(self):
        return iter(sorted(super(SortedDict, self).__iter__()))

    def items(self):
        return iter((k, self[k]) for k in self)

fruits = SortedDict({3: "banana",
          4: "grapes",
          1: "apple",
          2: "cherry"})

for each in fruits:
    print each, fruits[each]

Complete working implementation is here

edited May 23 '17 at 12:20

Community

1
1

answered Feb 15 '14 at 06:39

thefourtheye

233,700
52
457
497

I never wanted to implement a sorted dict, I was asking to see if the behavior I mentioned above was a normal occurrence in python. – Feb 15 '14 at 07:10
2

@user3058846 No it is NOT. Because in this case, small integers in the range (-5, 256) are used as keys which are internally cached and their hash values are the same as their own values. That is why they appear to be sorted already. Try `{300: "banana", 400: "grapes", 1000: "apple", 2000: "cherry"}` – thefourtheye Feb 15 '14 at 07:14

mhlester · Answer 2 · 2014-02-15T07:28:23.230

2

From the docs:

Keys and values are listed in an arbitrary order which is non-random, varies across Python implementations, and depends on the dictionary’s history of insertions and deletions.

edited Feb 15 '14 at 07:28

answered Feb 15 '14 at 06:40

mhlester

22,781
10
52
75

"They are ordered by their hash" - no, they're not, though it may appear that way sometimes. – user2357112 Feb 15 '14 at 06:52
If that's true, then why does it give the error `"unhashable type"` when trying to assign with a key like a list? – mhlester Feb 15 '14 at 07:21
1

The hash values are used to locate an entry in a dict, but the entries are not sorted by hash. It's significantly more complex than that. Among other things, hash values are reduced to their last `n` bits for a hash table with `2**n` spaces, and there's a [100-line comment](http://hg.python.org/cpython/file/7c47529bda0e/Objects/dictobject.c#l33) in the source explaining the subtleties of Python's collision resolution. – user2357112 Feb 15 '14 at 07:26

score 0 · Answer 3 · answered Feb 15 '14 at 06:56

Iteration over a dict is not guaranteed to produce any particular order. In particular, it is not guaranteed to be sorted, it is not guaranteed to be in insertion order, it may be different between equal dicts, and it may be different from one execution of the interpreter to another. Here's an example:

>>> dict.fromkeys([-1, -2])
{-2: None, -1: None}
>>> dict.fromkeys([-2, -1])
{-1: None, -2: None}

Two equal dicts, two different orders. Neither dict is in the order the keys were inserted in, and the second dict's keys aren't in sorted order.

If you want to iterate over the keys in sorted order, use

for key in sorted(d)

If you want to iterate over the keys in the order they were inserted in, use a collections.OrderedDict.

score 0 · Answer 4 · answered Feb 15 '14 at 09:04

Besides OrderedDict, you can just use the built-in sorted function to iterate a dict:

fruits = {3: "banana",
      4: "grapes",
      1: "apple",
      2: "cherry"}

for each in sorted(fruits.items(), key=lambda i:i[0]):
      print each[0], each[1]

BTW, sorted() returns a two element tuple list, not a dict.

score 0 · Answer 5 · answered Sep 23 '14 at 07:10

As the docs state, no, keys are not sorted in a Python dict. But many people have found that behavior useful and there exist many implementations of sorted dicts on PyPI. The SortedDict data type does exactly what you observed: efficiently maintains its keys in sorted order.

One such implementation is the sortedcontainers module which provides sorted list, sorted dict, and sorted set data types. It's implemented in pure-Python but is fast-as-C implementations. Unit tests provide 100% coverage and it's passed hours of stress testing.

Perhaps most importantly, sortedcontainers maintains a performance comparison of several popular implementations along with a description of their tradeoffs.

Are sorted keys guaranteed by a Python dictionary?

5 Answers5