2.1: Introduction
- Page ID
- 17022
A dictionary is like a list, but more general. In a list, the indices have to be integers; in a dictionary they can be (almost) any type.
You can think of a dictionary as a mapping between a set of indices (which are called keys) and a set of values. Each key maps to a value. The association of a key and a value is called a key-value pair or sometimes an item.
As an example, we’ll build a dictionary that maps from English to Spanish words, so the keys and the values are all strings.
The function dict
creates a new dictionary with no items. Because dict
is the name of a built-in function, you should avoid using it as a variable name.
>>> eng2sp = dict() >>> print eng2sp {}
The squiggly-brackets, {}
, represent an empty dictionary. To add items to the dictionary, you can use square brackets:
>>> eng2sp['one'] = 'uno'
This line creates an item that maps from the key ’one’
to the value 'uno'
. If we print the dictionary again, we see a key-value pair with a colon between the key and value:
>>> print eng2sp {'one': 'uno'}
This output format is also an input format. For example, you can create a new dictionary with three items:
>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}
But if you print eng2sp
, you might be surprised:
>>> print eng2sp {'one': 'uno', 'three': 'tres', 'two': 'dos'}
The order of the key-value pairs is not the same. In fact, if you type the same example on your computer, you might get a different result. In general, the order of items in a dictionary is unpredictable.
But that’s not a problem because the elements of a dictionary are never indexed with integer indices. Instead, you use the keys to look up the corresponding values:
>>> print eng2sp['two'] 'dos'
The key ’two’
always maps to the value 'dos'
so the order of the items doesn’t matter.
If the key isn’t in the dictionary, you get an exception:
>>> print eng2sp['four'] KeyError: 'four'
The len
function works on dictionaries; it returns the number of key-value pairs:
>>> len(eng2sp) 3
The in
operator works on dictionaries; it tells you whether something appears as a key in the dictionary (appearing as a value is not good enough).
>>> 'one' in eng2sp True >>> 'uno' in eng2sp False
To see whether something appears as a value in a dictionary, you can use the method values
, which returns the values as a list, and then use the in
operator:
>>> vals = eng2sp.values() >>> 'uno' in vals True
The in
operator uses different algorithms for lists and dictionaries. For lists, it uses a search algorithm, as in Section 8.6. As the list gets longer, the search time gets longer in direct proportion. For dictionaries, Python uses an algorithm called a hashtable that has a remarkable property: the in
operator takes about the same amount of time no matter how many items there are in a dictionary. I won’t explain how that’s possible, but you can read more about it at http://en.Wikipedia.org/wiki/Hash_table.
Exercise \(\PageIndex{1}\)
Write a function that reads the words in words.txt
and stores them as keys in a dictionary. It doesn’t matter what the values are. Then you can use the in
operator as a fast way to check whether a string is in the dictionary.
If you did Exercise 10.15.6, you can compare the speed of this implementation with the list in
operator and the bisection search.