Class 49: Dictionaries

Held Monday, November 27, 2000

Summary

Today we move on to a new kind of ADT, the Dictionary. Like arrays, dictionaries provide indexed access to elements. Unlike arrays, dictionaries use strings (or arbitrary values) as the index values.

Notes

• I hope you had a good Thanksgiving.
• I brought back stress-relief presents
• Are there any questions on exam 3.
  • I've had some questions about sorted lists. When I say ``Iterate in order'', I mean ``iterate in order, from smallest to largest''.
  • Ask yourself whether it really makes sense to add something to the end of a sorted list if there's no way to access it as the last element (or is there?).
• Updates on search

Overview

• Assocation lists, revisited
• Generalizing Association lists: Dictionaries
• Building a Dictionary ADT
• Implementing the Dictionary ADT with Association lists

Association Lists

• Let's reflect back on one of your favorite data structures from 151, the association list, and see both how we can describe it as an ADT and what other implementations we can identify.
• Warning! I'll ask you for the list of things we talk about when designing ADTS and Data Structures.

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, whatever).
• Collections of objects indexed by objects are called dictionaries.
  • Some people also refer to them as keyed tables.
• 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.

Dictionaries, Revisited

• How do we do build dictionaries? There are a number of techniques, including linked lists of key/value pairs. and 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 a list.
• Search through the list step by step.
• We may develop code in class.