Class 37: Dictionaries (1)

Held: Friday, 5 November 2004

Summary: Today we begin discussion of a new abstract data type, the Dictionary. Dictionaries provide indexed access to values in which the indices may be a variety of objects (most typically strings).

Related Pages:

• EBoard.
• Sample Code.

Notes:

• You've just spent a lot of time on the exam and are also working on the project, so there is no homework for Monday.

Overview:

• Introduction to dictionaries
• Applications of dictionaries
• A Dictionary ADT
• Comparing dictionaries and databases
• Implementing dictionaries with arrays

An Introduction to Dictionaries

• In our investigation of vectors and arrays, we've seen structures that collect objects in which the objects can be indexed by numbers.
• Are there other ways to index collections? Yes, we could index collections by strings.
• We could also index by other objects (Strings, Integers, Points, whatever).
• Collections of objects indexed by objects are called dictionaries.
  • Some people also refer to them as keyed tables.
  • Other people refer to them as maps
• Some more terminology:
  • The objects we're using as indices are called keys.
  • The objects we're looking up are called values.

Applications of Dictionaries

• Why do we do we want dictionaries? They make many tasks more convenient.
• Keeping track of objects we've seen. If an object is an index in the dictionary, we've seen it; if it's not an index in the dictionary, we haven't seen it. This would be helpful for our puzzle solver.
• Counting things We can use the dictionary to associate a counter with each object; when you see another copy, increment the counter.
• Databases. There are a number of techniques for implementing and thinking about databases. Dictionaries provide a simple mechanism for single-keyed databases.
• The project. We can use dictionaries to associate objects with their names.

Dictionaries, Revisited

• How do we do implement dictionaries? There are a number of techniques, including arrays of key/value pairs.
• For now, we'll focus on designing the ADT and we won't worry about how they work. Later, we'll look at how to build them.
• What features do we need in a dictionary? Some are similar to those we need for vectors.
  • Add something to the dictionary (requires a key and value).
  • Look up something in the dictionary (requires a key, returns a value).
  • Remove something from the dictionary.
• Others correspond more to the different structure of dictionaries.
  • List/iterate all the keys in the dictionary.
  • List/iterate all the values in the dictionary.

Dictionaries vs. Databases

• Note that dictionaries are not the same as databases.
• Why not? There are a number of reasons.
• Dictionaries have a single key, and that key provides the only way to access information.
  • Databases may have multiple keys. You may also access information using other fields. For example, while a database may be keyed by ID#, you might still be able to search by name.
• A dictionary returns a single object given a request.
  • A database may return multiple objects (e.g., all the students with a B).

Implementing Dictionaries with Association Lists

• Use a simple KeyedValue structure (that stores a key and a value).
• Shove 'em in an array.
• Search through the array step by step.
• Other variants:
  • Keep the values ordered.

Binary Search Trees

• We can also apply the divide-and-conquer strategy to this data structure.
• That is, we'll put the values in a tree.
• Here's a way of making the search potentially more efficient: The BST property: The keys of all left descendants are less than the key of the root; The keys of all right decendants are greater than the key of the root.
• If the tree is balanced, adding and searching are O(logn)
• But trees can be easily unbalanced.
• Keeping trees balanced is a topic for CSC301.