Are the integer keys in a Python dictionary sorted and sorted with priority?

Question

I'm using python 2.7.5 on OS X Mavericks and I'm seeing unexpected behavior with a dictionary I'm using to generate a simple text menu. My question is: are the integer keys in a Python dictionary sorted and sorted with priority? I can see that the mainMenu_1 dictionary (containing some numeric keys and some string keys) sorts the integer keys and then presents the string keys in the expected random order. mainMenu_2 is randomized as expected.

from the python 2.7.8 docs:

"It is best to think of a dictionary as an unordered set of key: value pairs, with the requirement that the keys are unique (within one dictionary)."

mainMenu_1 = {
   0: 'README',
   1: 'New Set',
   2: 'View Sets',
   3: 'Quiz',
   4: 'Scores',
   5: 'Configuration Settings',
   'Q': 'Quit',
   'a': 'additional letter to test',
   'b': 'additional letter to test'
}

mainMenu_2 = {
   'one': 'README',
   'two': 'New Set',
   'three': 'View Sets',
   'four': 'Quiz',
   'five': 'Scores',
   'six': 'Configuration Settings',
   'Q': 'Quit',
   'd': 'another letter to test'
}

print mainMenu_1.keys()
[0, 1, 2, 3, 4, 5, 'a', 'Q', 'b']
print mainMenu_2.keys()
['four', 'Q', 'five', 'three', 'd', 'six', 'two', 'one']

And a third test:

c = {1:'one','two':'two',3:'three'}
print c
{1: 'one', 3: 'three', 'two': 'two'}

Python auto hashes the dictionary inorder to reduce the time order complexity of lookup — Ashoka Lella, Sep 11 '14 at 17:09
There's no guarantee that a dictionary will be ordered. If you want that behavior, use an OrderedDict. — user3557327, Sep 11 '14 at 17:42
If you want a more detailed explanation of how python stores key/value pairs, have a look at this article : http://www.laurentluce.com/posts/python-dictionary-implementation/ — doubleo, Sep 11 '14 at 18:46
Ned, at the time, I meant that integer keys seemed to be come first when you print or iterate through the dict, and in a sorted order. I can see that this isn't the case now. — foundling, Sep 13 '14 at 14:52
Very related: http://stackoverflow.com/questions/12165200/order-of-unordered-python-sets — mgilson, Sep 09 '15 at 16:52

roippi · Accepted Answer · 2014-09-12T17:30:40.183

dicts are "sorted" (quotation fingers heavily used) according to their underlying hash table buckets. The hash() of an integer is itself:

hash(42)
Out[29]: 42

...but that doesn't necessarily mean that lower integers will appear before higher ones since the hash is taken modulo table size in order to allocate it to a bucket.

d = {i:i for i in range(250,260)}

print(d)
{256: 256, 257: 257, 258: 258, 259: 259, 250: 250, 251: 251, 252: 252, 253: 253, 254: 254, 255: 255}

So contiguous integers are not necessarily sorted in a dict. And as for integers getting priority, no, there's nothing special about integers. Their hash values just clump together particularly well, and you happened to pick some strings that hashed larger (again, modulo table size) than that clump.

hash('roippi')
Out[26]: 8915818834981308633

hash('roippi') % 8 # min hashtable size in py2 is 3-bit
Out[27]: 1

d = {0:'', 'roippi':0, 2:0}

print(d)
{0: '', 'roippi': 0, 2: 0}

All of this is of course an implementation detail of cPython, so the only thing that is guaranteed is that ordering is "arbitrary but consistent¹".

¹consistent, at least, across a single run of the python interpreter. 3.2.3+ randomly seeds the hash of certain (non-int) types, and earlier versions will also do so if run with the -R flag.

Consider if this answer need to be updated for "preserves order" behavior of Python 3.6+ — Alexei Levenkov, Feb 26 '22 at 00:14

score 2 · Answer 2 · answered Sep 11 '14 at 17:09

According to some simple tests I have just executed, it is indeed like you say - and I was testing it in Python 3.4.0

I don't know the reason for which that happens. I see no reason though to think of

"It is best to think of a dictionary as an unordered set of key: value pairs, with the requirement that the keys are unique (within one dictionary)."

as misleading or untrue in any way. This is perfectly right: even though we can see there's some sorting going on behind the scenes, you should never rely on it. That's why the docs say what they say. They could just as well sort integer keys backwards and nobody should care - your implementations cannot rely on that mechanism.

That said - still a nice find!

Are the integer keys in a Python dictionary sorted and sorted with priority?

2 Answers2

Linked

Related