Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

  




 

 

Chapter 15. Mappings and Dictionaries

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.

Dictionary Semantics

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 http://www.voidspace.org.uk/python/odict.html.


 
 
  Published under the terms of the Open Publication License Design by Interspire