Cannot predict iterkeys() output order

Question

Question: Why does EXIT appear as the first line of my output?

Let me preface this by saying that I wrote this code while experimenting on solving a particular problem in a python script I am writing. So, yes, I am aware that this code may look rather ugly.

I cannot figure out why EXIT is shown first. I've even tried moving 'Quit' : 'EXIT' to the beginning of the dict (before 'Settings', but it still displays the same. I can't tell whether has something to do with the nature of iterkeys or dictionaries in general.

At first, my guess was that it might have something to do with the fact that mmenu['Quit'] is a string and mmenu['Settings'] is a dict, but then I noticed how the following is outputted in this order:

Rename: Enter a new name
Where?
Delete: Select Menu Item to Delete

when they were coded as:

'Rename': 'Rename: Enter a new name', 
'Delete': 'Delete: Select Menu Item to Delete', 
'Move_Item': 'Where?'

but what I can't figure out is why that matters.

Any insight is appreciated :)

#!/usr/bin/python
from inspect import isfunction

def create():
  print "create function: you've just created a menu"
  pass

mmenu = {
  'Settings': 
    {
    'Edit': 
      {
      'Create': create, 
      'Modify': 
    {
    'Rename': 'Rename: Enter a new name', 
    'Delete': 'Delete: Select Menu Item to Delete', 
    'Move_Item': 'Where?'
    }
      }, 
    'Default_Settings': 'Default Settings'}, 
  'Quit' : 'EXIT'
  }

nmenu = mmenu
omenu = {}

def dictloop(dmenu):
  global omenu
  nmenu = dmenu
  for key in nmenu.iterkeys():
    if isfunction(nmenu[key]):
      nmenu[key]()
    if type(nmenu[key]) is str:
      print nmenu[key]
    if type(nmenu[key]) is dict:
      omenu = nmenu[key]
      dictloop(omenu)

dictloop(nmenu)

OUTPUT:

EXIT
create function: you've just created a menu
Rename: Enter a new name
Where?
Delete: Select Menu Item to Delete
Default Settings

A dictionary is a set of key,value pairs and a set is an unordered collection of items. Perhaps you need a list of lists? or at least not a dictionary. — perreal, Feb 03 '14 at 08:23
Python dicts are hash tables, so there is no notion of order. If you want to keep your items in order, choose a different data structure (say `OrderedDict` from collections). — michaelmeyer, Feb 03 '14 at 08:23
"Cannot predict iterkeys() output order" - that's a pretty good summary of the answer, too. You can't predict the `iterkeys` output order. It's just some order. — user2357112, Feb 03 '14 at 08:30
I hear what you guys are saying about there being no notion of order, but Python clearly has a predictable sequence in which it processes this dict, because it displays the same result every time. I'm just trying to figure out why it decided to display the string before the nested dict. — holaymolay, Feb 03 '14 at 08:31
@holaymolay, the order depends on the algorithm used for hashing keys, it is consistent but not predictable — perreal, Feb 03 '14 at 08:32
It's only consistent for one particular dictionary, and only until you add or remove any keys. Equal dictionaries might have different iteration orders, and the same exact sequence of modifications might result in a different iteration order on a different interpreter execution. — user2357112, Feb 03 '14 at 08:38
@perreal, okay this mostly answers my question. So does that mean iterkeys, even though it is involved, is really not the culprit? — holaymolay, Feb 03 '14 at 08:39
@holaymolay, yes it is not, you can use an ordered dictionary, or also push the keys in a list also to track the order yourself. For this particular example I would use list of lists. — perreal, Feb 03 '14 at 08:42
@user2357112, aah okay. Your first response through me for a loop, you've made it clearer now. Thanks! — holaymolay, Feb 03 '14 at 08:44
@perreal, perfect, you've been a big help. I will give it a try. — holaymolay, Feb 03 '14 at 08:46

Kevin · Answer 1 · 2014-02-03T09:23:20.883

Here is the method that Python uses for creating an order for its dict:

Create a list in memory bigger than the dict, whose size of a power of 2 (e.g. 32)
Hash the strings from the dict
Use a mask to retrieve a small part of each hash (e.g. hash('x') & 31)
Use this value as the index for storing the original string in the list

Several of the positions in the list will be empty, so this method does not use memory efficiently, but it means that the position of any item from the dictionary can be retrieved in one calculation vice using a binary search. (e.g. hash('x')&31 == index for key['x'])

There is a good description of the process here: http://www.laurentluce.com/posts/python-dictionary-implementation/

Cannot predict iterkeys() output order

1 Answers1