Many algorithms need to map a key to a data value. This kind of
mapping is supported by the Python dictionary,
dict. We'll look at dictionaries from a number of
viewpoints: semantics, literal values, operations, comparison operators,
statements, built-in functions and methods.
We are then in a position to look at two applications of the
dictionary. We'll look at how Python uses dictionaries along with
sequences to handle arbitrary lists of parameters
to functions in the section called "Advanced Parameter Handling For Functions". This is a very
sophisticated set of tools that let us define functions that are very
flexible and easy to use.
A dictionary, called a dict, maps a
key to a value. The key
can be any type of Python object that computes a consistent hash value.
The value referenced by the key can be any type of Python object.
There is a subtle terminology issue here. Python has provisions
for creating a variety of different types of mappings. Only one type of
mapping comes built-in; that type is the dict.
The terms are almost interchangeable. However, you may develop or
download other types of mappings, so we'll be careful to focus on the
dict class.
Working with a dict is similar to working
with a sequence. Items are inserted into the
dict, found in the dict
and removed from the dict. A
dict object has member methods that return a
sequence of keys, or values, or
(
key
,
value
)
tuples suitable for use in a
for
statement.
Unlike a sequence, a dict does not preserve
order. Instead of order, a dict uses a
hashing algorithm to identify a place in the
dict with a rapid calculation of the key's hash
value. The built-in function, hash is used to do
this calculation. Items in the dict are inserted
in an position related to their key's apparently random hash
values.
Later in this chapter we'll see how Python uses
tuples and dictionaries to handle variable
numbers of arguments to functions.
Some Alternate Terminology. A dict can be thought of as a container
of
(
key
:
value
)
pairs. This can be a helpful way to imagine the information in a
mapping. Each pair in the list is the mapping from a key to an
associated value.
A dict can be called an associative array.
Ordinary arrays, typified by sequences, use a numeric index, but a
dict's index is made up of the key objects. Each
key is associated with (or "mapped to") the appropriate value.
Some Consequences. Each key object has a hash value, which is used to place tje key
and the value in the dict. Consequently, the
keys must have consistent hash values; they must be immutable objects.
You can't use list or
dict objects as keys. You can use
tuple, string and
frozenset objects, since they are immutable.
Additionally, when we get to class definitions (in Chapter 21, Classes
), we can make arrangements for our objects
to return an immutable hash value.
A common programming need is a heterogeneous container of data.
Database records are an example. A record in a database might have a
boat's name (as a string), the length overall (as
a number) and an inventory of sails (a list of
strings). Often a record like this will have each
element (known as a field) identified by name. A
C or C++ struct accomplishes this. This kind of named collection of data
elements may be better handled with a class (someting we'll cover in
Chapter 21, Classes
). However, a mapping is also useful for
managing this kind of heterogeneous data with named fields.
Note that many languages make record definitions a
statically-defined container of named fields. A Python
dict is dynamic, allowing us to add field names
at run-time.
A common alternative to hashing is using some kind of ordered
structure to maintain the keys. This might be a tree or list, which
would lead to other kinds of mappings. For example, there is an ordered
dictionary, odict, that can be downloaded from
https://www.voidspace.org.uk/python/odict.html.