Dictionary Keys

[bumsfeld]

I can not figure out the order of dictionary keys, they seemed not to be sorted. Any insight?

[vegaseat]

An example would be nice, one that surprises you by the outcome.

[G-Do]

From the Dive Into Python tutorial:

"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 :-|

[bumsfeld]

Here are a bunch of impel dictionaries that surprise me:

dic1 = {'a':1, 'b':2, 'c':3, 'd':4}

print dic1  # {'a': 1, 'c': 3, 'b': 2, 'd': 4}

dic2 = {1:'a', 2:"b", 3:'c', 4:'d'}

print dic2  # {1: 'a', 2: 'b', 3: 'c', 4: 'd'}

dic3 = {11:'a', 22:"b", 3:'c', 4:'d'}

print dic3  # {3: 'c', 11: 'a', 4: 'd', 22: 'b'}

dic2 seems to behave as expected but dic1 and dic3 are surprise me.

[vegaseat]

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.

[bumsfeld]

So there is some order, but we don't know what Python uses to create this order?

That is muchly confusing!

[mawe]

Hi!

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

Regards, mawe

[vegaseat]

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.

[bumsfeld]

I think I get it! It is sinking in slowly into my yellow brains! So key is something more meaningfull then a just number.

[vegaseat]

By gosh, you got it! You may call this dictionary comprehension!

[bumsfeld]

Now my question is what kind of things can be used as key?

[vegaseat]

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!

[bumsfeld]

Since I can reverse dictionary, then anything that can be value can also be key?

[G-Do]

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).

Well, that's my experience, anyway ;)