## Dictionaries

Back to bird watching. Suppose we want to know how often each kind of bird was seen. Our first attempt uses a list of pairs, each a list storing the name of a bird and the number of times it has been seen so far:

import sys

for filename in sys.argv[1:]: infile = open(filename, 'r')

# For each bird, find its entry and increment the count, for line in infile:

name = line.strip() found = False for entry in birds:

infile.close()

for (name, count) in birds: print name, count

This gives the right answer, but there are two things wrong with it. The first is that it is complex. The more nested loops our programs contain, the harder they are to understand, fix, and extend. The second is that it is inefficient. Suppose we were interested in beetles instead of birds and that we had millions of observations of tens of thousands of species. Scanning the list of names each time we want to add one new observation would take a long, long time, even on a fast computer (a topic we will return to in Chapter 11, Searching and Sorting, on page 214).

Can we use a set to solve both problems at once? Sets can look up values in a single step; why not combine each bird's name and the number of times it has been seen into a two-valued tuple and put those tuples in a set?

The problem with this idea is that we can look for values only if we know what those values are. In this case, we won't. We will know only the name of the species, not how many times it has already been seen.

The right answer is to use another data structure called a dictionary. Also known as a map, a dictionary is an unordered mutable collection of key/value pairs (see Figure 9.5, on the following page). In plain English, dictionaries are like phone books. They associate a value (such as a phone number) with a key (like a name). The keys form a set. Any particular key can appear at most once in a dictionary, and like the elements in sets, keys must be immutable (though the values associated with them do not have to be).

Dictionaries are created by putting key/value pairs inside braces. To get the value associated with a key, we put the key in square brackets:

>>> birds = {'canada goose' : 3, 'northern fulmar' : 1} >>> birds

{'canada goose' : 3, 'northern fulmar' : 1} >>> birds[ 'northern fulmar'] 1

'northern fulmar'

'northern fulmar'

3 1

Figure 9.5: Structure of a dictionary

As you'd expect, the empty dictionary is written {}. Indexing a dictionary with a key it doesn't contain produces an error, just like an out-of-range index for a list:

>>> birds = {'canada goose' : 3, 'northern fulmar' : 1} >>> birds['canada goose'] 3

>>> birds['long-tailed jaeger'] Traceback (most recent call last):

File "<stdin>", line 1, in ? KeyError: 'long-tailed jaeger'

To test whether a key is in a dictionary, use k in d:

>>> birds = {'eagle' : 999, 'snow goose' : 33}

eagles have been seen >>> del birds[ 'eagle' ] >>> if 'eagle' in birds:

Updating and Membership

Updating dictionaries is easy. Just assign a value to a key. If the key is already in the dictionary, this changes the value associated with it.

if the key was not present, it is added, along with the value:

>>> birds[ 'snow goose'] = 33 >>> birds[ 'eagle'] = 999 # oops >>> birds

{'eagle' : 999, 'snow goose' : 33} >>> birds[ 'eagle' ] = 9 >>> birds

To remove an entry from a dictionary, use del d[k], where d is the dictionary and k is the key being removed. Only entries that are present can be removed; trying to remove one that isn't there causes an error: