CSC152 2006S, Class 37: Dictionaries (1): A Simple Implementation

Admin:
* Questions on the exam?
* Guest speaker tomorrow.
* EC for talk tomorrow at 4:30.  Unknown topic.
* Joke about cutting and pasting.

Overview:
* Dictionary basics.
* Labs.

Dictionaries:
* Arrays: Something that holds values and lets you access them by index.  Valid indices are 0 ... (length-1) [subset of positive integers].
* Dictionaries: Something that holds values and lets you access them by index.  Valid indices are "almost anything you want".  (strings, people, real number, points, ...)
* Dictionary grades = ...;
  grades.set("Davis", 60);
  grades.set("Dimitar", -10);
  grades.set("Angeline", 100);
* Dictionary lastNames = ...;
  grades.set("Ben", "Mendoza");
  grades.set("Elizabeth", "Anonymized");
  ...

* Terminology:
  * Index is called "Key"
  * Thing associated with an index "Value"

* The PAMI of Dictionaries
  * Philosophy - Like arrays, but using "anything you want as indices"
  * Applications - Like a real dictionary
  * Methods - put(K key, V value); V get(K key)
  * Implementations
    * Association List (list of key/value pairs)
    * Association Vector (vector of key/value pairs) [TODAY'S LAB]
    * Binary Search Tree (Tuesday)
    * Hash Table (Wednesday)

Lab!