[Tutor] Question about order in a dictionary

[Danny Yoo]

On Sun, 27 Jun 2004, Dick Moores wrote:

> if I enter
>
> D = {"a": "first letter", "b": "second letter", "c": "third letter",
>      "z": "last letter"}
>
> and then
>
> print D
>
> I get
>
> {'a': 'first letter', 'c': 'third letter', 'b': 'second letter', 'z':
> 'last letter'}
>
> Why does the order change?  I'm just beginning to understand
> dictionaries, and I suppose the order doesn't matter, but why would it
> change?


Hi Dick,

You're somewhat right: order isn't so relevant in a dictionary.  It turns
out that when we create a dictionary, like:

###
D = {"a": "first letter", "b": "second letter", "c": "third letter",
     "z": "last letter"}
###

then that actually does two things: it initializing the dictionary, and
then it adds an entry to that dictionary, for each key/value pair we've
typed in, in left-to-right order.

The gory details about this are in the Python Reference manual.  For the
curious, here's the reference: http://www.python.org/doc/ref/dict.html

This left-to-right part can actually make a difference: we might
accidently make a typo when we define the dictionary, and reuse a key that
we didn't mean to, like:

###
D = {"a": "first letter", "b": "second letter", "c": "third letter",
     "a": "oops!"}
###

then the dictionary that we get back is guaranteed to have the following
key/value pairs:

    ('c', 'third letter')
    ('b', 'second letter')
    ('a', 'oops!')

since Python will overwrite the first key/value pair with the last.


So order might possible matter when we're creating a dictionary, but that
wasn't exactly your question.  *grin*

What you're asking is: why does the dictionary display in a different
order: why are the entries all scrambled up?  Python is doing its own
organizing, behind the scenes, and it doesn't guarantee at all what order
we'll get back those key/value pairs when we print out a dictionary.

That is, we deliberately sacrifice an ordering.  It seems harsh, but in
return, Python guarantees that if we ask for a specific key from a
dictionary, we'll be able to get its corresponding value very very
quickly.  It becomes a snap for Python to give us:

    D['a']

almost immediately, because of technical details about how dictionaries
are implemented as "hashtables", a data structure from computer science.
We can talk about hashtables later, if you'd like.


But if we really care about order, we can use a list instead of a
dictionary:

###
>>> key_values = [ ('a', 'first letter'),
...                ('b', 'second letter'),
...                ('c', 'third letter'),
...                ('z', 'last letter') ]
>>>
>>> key_values
[('a', 'first letter'), ('b', 'second letter'), ('c', 'third letter'),
('z', 'last letter')]
###

This list, too, can contain key/value pairs, and once we print it out,
we'll see that order's preserved.  But searching for a particular value is
just slightly more work than a dictionary:

###
>>> def find_value(key, key_values):
...     """Given a key, and a key/value list, returns the associated
...        value.
...        If no such key is found, raises KeyError."""
...     for (k, v) in key_values:
...         if key == k:
...             return v
...     raise KeyError, key
...
>>>
>>> find_value('c', key_values)
'third letter'
>>> find_value('b', key_values)
'second letter'
###


I hope this helps!  Please feel free to ask more questions on any of this.