6.4 Dictionaries in Action

As Table 6-2 suggests, dictionaries are indexed by key, and nested dictionary entries are referenced by a series of indexes (keys in square brackets). When Python creates a dictionary, it stores its items in any order it chooses; to fetch a value back, supply the key that it is associated with. Let's go back to the interpreter to get a feel for some of the dictionary operations in Table 6-2.

6.4.1 Basic Dictionary Operations

In normal operation, you create dictionaries and store and access items by key:

% python
>>> d2 = {'spam': 2, 'ham': 1, 'eggs': 3}    # Make a dictionary.
>>> d2['spam']                               # Fetch value by key.
2
>>> d2                                       # Order is scrambled.
{'eggs': 3, 'ham': 1, 'spam': 2}

Here, the dictionary is assigned to variable d2; the value of the key 'spam' is the integer 2. We use the same square bracket syntax to index dictionaries by key as we did to index lists by offsets, but here it means access by key, not position.

Notice the end of this example: the order of keys in a dictionary will almost always be different than what you originally typed. This is on purpose—to implement fast key lookup (a.k.a. hashing), keys need to be randomized in memory. That's why operations that assume a left-to-right order do not apply to dictionaries (e.g., slicing, concatenation); you can only fetch values by key, not position.

The built-in len function works on dictionaries too; it returns the number of items stored away in the dictionary, or equivalently, the length of its keys list. The dictionary has_key method allows you to test for key existence, and the keys method returns all the keys in the dictionary, collected in a list. The latter of these can be useful for processing dictionaries sequentially, but you shouldn't depend on the order of the keys list. Because the keys result is a normal list, however, it can always be sorted if order matters:

>>> len(d2)                    # Number of entries in dictionary
3
>>> d2.has_key('ham')          # Key membership test (1 means true)
1
>>> 'ham' in d3                # Key membership test alternative
1
>>> d2.keys(  )                  # Create a new list of my keys.
['eggs', 'ham', 'spam']

Notice the third expression in this listing: the in membership test used for strings and lists also works on dictionaries—it checks if a key is stored in the dictionary, like the has_key method call of the prior line. Technically, this works because dictionaries define iterators that step through their keys lists. Other types provide iterators that reflect their common uses; files, for example, have iterators that read line by line; more on iterators in Chapter 14 and Chapter 21.

In Chapter 10, you'll see that the last entry in Table 6-2 is another way to build dictionaries by passing lists of tuples to the new dict call (really, a type constructor), when we explore the zip function. It's a way to construct a dictionary from key and value lists in a single call.

6.4.2 Changing Dictionaries in-Place

Dictionaries are mutable, so you can change, expand, and shrink them in-place without making new dictionaries, just like lists. Simply assign a value to a key to change or create the entry. The del statement works here too; it deletes the entry associated with the key specified as an index. Notice the nesting of a list inside a dictionary in this example (the value of key "ham"); all collection data types in Python can nest inside each other arbitrarily:

>>> d2['ham'] = ['grill', 'bake', 'fry']      # Change entry.
>>> d2
{'eggs': 3, 'spam': 2, 'ham': ['grill', 'bake', 'fry']}

>>> del d2['eggs']                            # Delete entry.
>>> d2
{'spam': 2, 'ham': ['grill', 'bake', 'fry']}

>>> d2['brunch'] = 'Bacon'                    # Add new entry.
>>> d2
{'brunch': 'Bacon', 'spam': 2, 'ham': ['grill', 'bake', 'fry']}

As with lists, assigning to an existing index in a dictionary changes its associated value. Unlike lists, whenever you assign a new dictionary key (one that hasn't been assigned before), you create a new entry in the dictionary, as was done in the previous example for key 'brunch'. This doesn't work for lists, because Python considers an offset out of bounds if it's beyond the end of a list, and throws an error. To expand a list, you need to use such tools as the append method or slice assignment instead.

6.4.3 More Dictionary Methods

Besides has_key, dictionary methods provide a variety of tools. For instance, the dictionary values and items methods return lists of the dictionary's values and (key,value) pair tuples, respectively.

>>> d2.values(  ), d2.items(  )
([3, 1, 2], [('eggs', 3), ('ham', 1), ('spam', 2)])

Such lists are useful in loops that need to step through dictionary entries one by one. Fetching a nonexistent key is normally an error, but the get method returns a default value (None, or a passed-in default) if the key doesn't exist.

>>> d2.get('spam'), d2.get('toast'), d2.get('toast', 88)
(2, None, 88)

The update method provides something similar to concatenation for dictionaries; it merges the keys and values of one dictionary into another, blindly overwiting values of the same key:

>>> d2
{'eggs': 3, 'ham': 1, 'spam': 2}
>>> d3 = {'toast':4, 'muffin':5}
>>> d2.update(d3)
>>> d2
{'toast': 4, 'muffin': 5, 'eggs': 3, 'ham': 1, 'spam': 2}

Dictionaries also provide a copy method; more on this method in the next chapter. In fact, dictionaries come with more methods than those listed in Table 6-2; see the Python library manual or other documentation sources for a comprehensive list.

6.4.4 A Languages Table

Here is a more realistic dictionary example. The following example creates a table that maps programming language names (the keys) to their creators (the values). You fetch a creator name by indexing on language name:

>>> table = {'Python':  'Guido van Rossum',
...          'Perl':    'Larry Wall',
...          'Tcl':     'John Ousterhout' }
...
>>> language = 'Python'
>>> creator  = table[language]
>>> creator
'Guido van Rossum'

>>> for lang in table.keys(  ): 
...     print lang, '\t', table[lang]
...
Tcl     John Ousterhout
Python  Guido van Rossum
Perl    Larry Wall

The last command uses a for loop, which we haven't covered yet. If you aren't familiar with for loops, this command simply iterates through each key in the table and prints a tab-separated list of keys and their values. See Chapter 10 for more on for loops.

Because dictionaries aren't sequences, you can't iterate over them directly with a for statement, in the way you can with strings and lists. But if you need to step through the items in a dictionary it's easy: calling the dictionary keys method returns a list of all stored keys you can iterate through with a for. If needed, you can index from key to value inside the for loop as done in this code.

Python also lets us step through a dictionary's keys list without actually calling the keys method in most for loops. For any dictionary D, saying for key in D: works the same as saying the complete for key in D.keys( ):. This is really just another instance of the iterators mentioned earlier, which allow the in membership to work on dictionaries as well.

6.4.5 Dictionary Usage Notes

Here are a few additional details you should be aware of when using dictionaries:

• Sequence operations don't work. Dictionaries are mappings, not sequences; because there's no notion of ordering among their items, things like concatenation (an ordered joining) and slicing (extracting contiguous section) simply don't apply. In fact, Python raises an error when your code runs, if you try to do such things.

• Assigning to new indexes adds entries. Keys can be created either when you write a dictionary literal (in which case they are embedded in the literal itself), or when you assign values to new keys of an existing dictionary object. The end result is the same.

• Keys need not always be strings. Our examples used strings as keys, but any other immutable objects (not lists) work just as well. In fact, you could use integers as keys, which makes a dictionary look much like a list (when indexing, at least). Tuples are sometimes used as dictionary keys too, allowing for compound key values. And class instance objects (discussed in Part VI) can be used as keys too, as long as they have the proper protocol methods; roughly, they need to tell Python that their values won't change, or else they would be useless as fixed keys.

6.4.5.1 Using dictionaries to simulate flexible lists

When you use lists, it is illegal to assign to an offset that is off the end of the list:

>>> L = [  ]
>>> L[99] = 'spam'
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
IndexError: list assignment index out of range

Although you could use repetition to pre-allocate as big a list as you'll need (e.g., [0]*100), you can also do something that looks similar with dictionaries, which does not require such space allocations. By using integer keys, dictionaries can emulate lists that seem to grow on offset assignment:

>>> D = {  }
>>> D[99] = 'spam'
>>> D[99]
'spam'
>>> D
{99: 'spam'}

Here, it almost looks as if D is a 100-item list, but it's really a dictionary with a single entry; the value of key 99 is the string 'spam'. You're able to access this structure with offsets much like a list, but you don't have to allocate space for all the positions you might ever need to assign values to in the future.

6.4.5.2 Using dictionaries for sparse data structures

In a similar way, dictionary keys are also commonly leveraged to implement sparse data structures—for example, multidimensional arrays, where only a few positions have values stored in them:

>>> Matrix = {  }
>>> Matrix[(2,3,4)] = 88
>>> Matrix[(7,8,9)] = 99
>>>
>>> X = 2; Y = 3; Z = 4              # ; separates statements.
>>> Matrix[(X,Y,Z)]
88
>>> Matrix
{(2, 3, 4): 88, (7, 8, 9): 99}

Here, we use a dictionary to represent a three-dimensional array, all of which are empty except for the two positions, (2,3,4) and (7,8,8). The keys are tuples that record the coordinates of nonempty slots. Rather than allocating a large and mostly empty three-dimensional matrix, we can use a simple two-item dictionary. In this scheme, accessing empty slots triggers a nonexistent key exception—these slots are not physically stored:

>>> Matrix[(2,3,6)]
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
KeyError: (2, 3, 6)

If we want to fill in a default value instead of getting an error message here, there are at least three ways we can handle such cases. We can either test for keys ahead of time in if statements, use the try statement to catch and recover from the exception explicitly, or simply use the dictionary get method shown earlier to provide a default for keys that do not exist:

>>> if Matrix.has_key((2,3,6)):     # Check for key before fetch.
...     print Matrix[(2,3,6)]
... else:
...     print 0
...
0
>>> try:
...     print Matrix[(2,3,6)]       # Try to index.
... except KeyError:                # Catch and recover.
...     print 0
...
0 
>>> Matrix.get((2,3,4), 0)          # Exists; fetch and return.
88 
>>> Matrix.get((2,3,6), 0)          # Doesn't exist; use default arg.
0

We'll study the if and try statements later.

6.4.5.3 Using dictionaries as "records"

As you can see, dictionaries can play many roles in Python. In general, they can replace search data structures (since indexing by key is a search operation), and represent many types of structured information. For example, dictionaries are one of many ways to describe the properties of an item in your program's domain; they can serve the same role as "records" or "structs" in other languages:

>>> rec = {  }
>>> rec['name'] = 'mel'
>>> rec['age']  = 41
>>> rec['job']  = 'trainer/writer'
>>>
>>> print rec['name']
mel

This example fills out the dictionary by assigning to new keys over time. Especially when nested, Python's built-in data types allow us to easily represent structured information:

>>> mel = {'name': 'Mark',
...        'jobs': ['trainer', 'writer'],
...        'web':  'www.rmi.net/~lutz',
...        'home': {'state': 'CO', 'zip':80501}}

This example uses a dictionary to capture object properties again, but has coded it all at once (rather than assigning to each key separately), and has nested a list and a dictionary to represent structure property values. To fetch components of nested objects, simply string together indexing operations:

>>> mel['name']
'Mark'
>>> mel['jobs']
['trainer', 'writer']
>>> mel['jobs'][1]
'writer'
>>> mel['home']['zip']
80501

Finally, note that more ways to build dictionaries may emerge over time. In Python 2.3, for example, the calls dict(name='mel', age=41) and dict([('name,'bob'), ('age',30)]) also build two-key dictionaries. See Chapter 10, Chapter 13, and Chapter 27 for more details.

Why You Will Care: Dictionary Interfaces Besides being a convenient way to store information by key in your programs, some Python extensions also present interfaces that look and work the same as dictionaries. For instance, Python's interface to dbm access-by-key files looks much like a dictionary that must be opened; strings are stored and fetched using key indexes: import anydbm file = anydbm.open("filename") # Link to file. file['key'] = 'data' # Store data by key. data = file['key'] # Fetch data by key. Later, you'll see that we can store entire Python objects this way too, if we replace anydbm in the above with shelve (shelves are access-by-key databases of persistent Python objects). For Internet work, Python's CGI script support also presents a dictionary-like interface; a call to cgi.FieldStorage yields a dictionary-like object, with one entry per input field on the client's web page: import cgi form = cgi.FieldStorage( ) # Parse form data. if form.has_key('name'): showReply('Hello, ' + form['name'].value) All of these (and dictionaries) are instances of mappings. More on CGI scripts later in this book.