"Dictionaries have no concept of order among elements. It is incorrect to say that the elements are 'out of order'; they are simply unordered. This is an important distinction which will annoy you when you want to access the elements of a dictionary in a specific, repeatable order (like alphabetical order by key). There are ways of doing this, they're just not built into the dictionary."

If you want a dictionary-type object with built-in sorting, you may have to write your own :-|

This little test using your example will show you that dictionary keys do have a certain order ...

# these all give the same result = {'a': 1, 'c': 3, 'b': 2, 'd': 4}
# so there must be a reason why keys are in a certain order!
dic11 = {'a':1, 'b':2, 'c':3, 'd':4}
print dic11
dic12 = {'a':1, 'd':4, 'b':2, 'c':3}
print dic12
dic13 = {'c':3, 'a':1, 'd':4, 'b':2}
print dic13

My reasoning would be that dictionary keys are ordered to make the lookup most efficient, a hash algorithm converting the key into an integer value would give such efficiency. I have not seen any official word on this.

Well, a dictionary (some call it hash) is per definition unordered. If you need it in some specific order, use another data structure, or just sort it ;) e.g.

d = {'a': 1, 'c': 3, 'b': 2}
for key in sorted(d.keys()):
print "%s => %s" % (key, d[key])
# will print
#a => 1
#b => 2
#c => 3

Look at it this way, a list assigns a numeric index to its elements. It starts at zero for the first element and then increases by one for each following element. To access the element you need to know this index number.

In the dictionary this index number has been replaced by a key, in many cases more meaningful then a number. So you don't really need an order, you need this key to access the associated value. The keys might have a perceived order, but it's not of any use.

If you want a quick sorted look of all your keys, go ahead and sort them like mawe has suggested.

I would use strings, even when you make something like a phone-number:name dictionary. You could use integers, but strings can be made more readable with the phone numbers. There are some scientific applications where an integer is better. Remember keys have to be unique!

If memory serves, dictionary keys must be immutable data types, and dictionary values can be mutable or immutable. This means that mutable data types like lists can be values, but not keys.

In addition to strings and number data types, you can also use tuples as keys. This can be incredibly useful if you ever need to represent higher-order sparse matrices. Suppose you need to represent a 4D matrix, with cells described by four indices i,j,k,l. This is a lot more complicated than a regular 2D matrix, which has just two indices, i and j (for the row and the column). You could try to represent the 4D beast using a list of lists of lists of lists, but that representation can get a little hairy, especially if the matrix needs to be sparse (certain elements are guaranteed to be duplicates, and are thus not included to save space - a valid plan of action when you're doing heavy-duty computations on large matrices). A much cleaner choice is to represent it using a dictionary, where each key is the tuple of integer indices of the form (i,j,k,l).