CSC152 Class 37: The Dictionary ADT

Admin:
* Cool Swing dance tonight!
  * Check [Swing]
* Be nice and give blood 
* About printing
  * Make sure to check properties and set to "US Letter" rather than "A4"
  * In the little "Print Command Box" type
  	a2ps --sides=duplex
* No additional homework for Monday (work on project)
* Exams due NOW!

Overview:
* The Dictionary ADT philosophy
* Applications
* ADT: Methods
* Comparing to databases
* Implementing with arrays

/Philosophy of Dictionaries/

* Dictionaries are collections of objects which are indexed by other objects
  * Most typically, collections of values indexed by strings
* Terminology:
  * The index is usually called a "key"
  * The associated value is usually called a "value"

/Why are such ADTs useful?/

* For the project!
* A lot of applications in which we access information by one portion of the informatino (e.g., phone books): Really Simple Databases
  * Some of you may recall the "sidekicks" example from 151
* Some students have used dictionaries for counting applications
* Dictionaries can provide an implementation of set

/Methods/

* Object find(String key) or find(Object key)
* set(Object key, Object value)
* Design question: Is this more like arrays, in which the "get" method does not remove values, or like queues, in which we have separate "get" and "peek"?  (The former.)
* remove(Object key)
* Design question: Do all the keys have to be the same type?  We'll say "no" for our design.
* Design question: Can two objects share the same key?  No.
  * Dictionaries are like partial functions (maps, ...)
* Design question: Can one object share two keys?  Yes.
  set("latest-write-learner", "Eryn");
  set("favorite-swing-woman", "Eryn");
  remove("latest-write-learner");

/Implementation: The Data Structure(s)/

* How do we implement dictionaries?
* What strategy?
  * List of key/value pairs
  * Array of key/value pairs
* How do you find something, assuming that the array isn't sorted?
  * Look at the key of each pair, in order, until we find it or run out of values.
  * O(n)
* How do you add something?
  * Make a key/value pair and stick it on the end.
  * O(1)
  * Problem: What if the key was already there?
  * Solution: Search for an entry with the key first.  If it's there, replace the value in that entry.
  	for (int i = 0; i < this.numentries; i++) {
		if (this.entries[i].key.equals(key)) {
			this.entries[i].value = value;
			return;
		} // if
	} // for
  If the key was not found, shove it at the end
  	this.entries[this.numentries] = new KeyedValue(key,value);
	++this.numentries;
  * O(n)
  * Problem: What happens with removal?  Will we keep empty spaces?
* How should we implement remove?
  * Search for an entry with the key.  If it's there, copy the last value into that spot.
  * O(n)

* How do you find something, assuming that we find some natural way to keep the array sorted?
  * Binary search!
  * O(log2n)
* Set:
  * O(n): May need to shift everything to "make room"
* Remove
  * O(n): May need to shift everything to "fill a hole"

Next Week: Faster implementations!