Held: Wednesday, 13 November 2013

Back to Outline 39 - Priority Queues and their Basic Implementation. On to Outline 41 - Implementing Dictionaries with Arrays or Lists.

Summary

We consider an important ADT, the Dictionary (also called, Map, Table, Hash, and Associative Array). Dictionaries are collections of values that can be indexed by some kind of value (not necessarily integers between 0 and size-1).

Related Pages

• Code: examples/dictionaries
• EBoard (HTML) (PDF)

Overview

• Detour: Model-View-Controller.
• Review: Designing ADTs and Data Structures.
• A Dictionary ADT.
• Simple implementations of dictionaries.

Administrivia

• Homework 10 distributed.
• Reminder: Next Tuesday we're going to the Digital Commons roundtable.
• Upcoming extra credit opportunities:
  • Town Hall, today, noon or 7:30 p.m.
  • Learning from Alumni, Thursday, 2:15: Atul Gupta, Trustee
  • CS Extra, Thursday, 4:15: Hilary Mason '00
  • Evening chat with Hilary Mason '00, Thursday, 8-9 pm
  • National Philanthropy Day, Friday (Donate to a charity of your choice)
  • NO CS TABLE THIS WEEK!
  • Innovation Class, Friday, 12:45, ARH 302, Hilary Mason '00
  • Career Connections with Hilary Mason '00, Friday, 4:15-6:30 (???)
  • Swim meet, Saturday, 3pm
  • Digital Commons talk, Monday, November 18, 7:00 p.m. or so
  • CS Department Talk, Wednesday, November 20, noon
  • "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101
  • "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302
  • Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]

Detour: Model-View-Controller

• How hard would it be for you to rewrite your calculator to have a graphical user interface (assuming we know how to make graphical user interfaces)?
• Ideally, when you think about problems like the calculator, you structure your program so that different parts are decoupled.
• One common approach is the model/view/controller, or MVC.
  • The model stores the data and does the real work.
  • The controller takes user input and sends commands to the model.
  • The view shows the state of the model, either because the model pushes the data to the view or because the view pulls data from the model.
• If you think about calculators through MVC, how might you design (or redesign) your calculator?

Review: ADT Design

• What are the things we think about as we design an ADT and the corresponding data structure.

A New ADT: Dictionaries

• "Like arrays, but indexed by whatever type of object your want."
• So, what methods would you include?
• What about iterators?
• Note that Dictionary is but one of a few names for this kind of data structures.
  • Some call it a Map, because it maps keys to values.
  • Some call it a Table, because they think of it as a key/value table.
  • Some call it a Hash, because one of the most popular implementations of dictionaries uses something called a hash table.
  • Some call it an Associative Array because it's like an array, and associates values with keys.
  • Wikipedia says that some people call this a Symbol Table, but I'll admit that I think of symbol tables as a more restricted type.

Implementing Dictionaries: The Basics

• Probably easiest to start with an unordered array or linked list.
• We'll store key/value pairs in the array of list.
• We can implement put by adding to the front of the linked list (or the back of the array).
• We can implement get by searching the linked list or array.
• How should we deal with a set for an element already in the array?