CODEWITHSUNDEEP
pythondictionary
foundling
foundling

Reputation: 1756

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

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'}

Upvotes: 3

Views: 1867

Answers (2)

roippi
roippi

Reputation: 25974

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 consistent1".

1consistent, 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.

Upvotes: 10

PawelP
PawelP

Reputation: 1180

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!

Upvotes: 2

Related Questions