CSC152 2005F, Class 45: Dictionaries (1): The Basics Admin: * No homework * Maybe prospectives * Extra credit for attending YGB Concert, Saturday, 19 Nov, 4pm * Extra credit for attending campus band concert, 8-10, Gardner * First home men's basketball game tonight, 7 pm. the *new!!!!* Darby Overview: * The PAMI of Dictionaries * Java's versions: Dictionary and Map * Implementation strategy one: Association List * Implementation strategy two: Binary Search Tree Philosophy of Dictionaries (Map) (KeyedTable) * Collection of values, indexed by the "reasonable" type of your choice (traditionally, strings) Terminology: We often say "key" for position" Methods: * put(KeyType key, OtherType value) * OtherType get(KeyType key) - does not remove; acts like "get" for Vectors or ArbityrarilyLarageIntegerArrays * No duplication of positions * Yes you may duplicate values * int size() * void remove(KeyType key) Application: Why? (Can focus on indexing by string) * Might want to build a dictionary (or Wikipedia) * Phone book, student directory, class list, etc: wide variety of cases in which we seem to use names as indices * Analysis of texts: Use strings to index counters Java makes our life to complex in its designs. Too bad. Implementation: * Strategy (from Scheme): Association list * Make a list of pairs * The car of each pair is the key * The cdr of each pair is the value * The built in operation assoc (and assq and assv, I think) searches for a key and returns the key/value pair. * In Java, make a Vector of these pairs KeyedValue(K,V) { K key; V value; } public AssociationList { Vector> contents; ... } * get is O(n) Look at each keyed value in the vector. If the key is equal to the key we want, return the value * Design question: What happens if the key doesn't appear - Return null - Throw exception public V get(K key) throws NoSuchKeyException { int len = contents.size(); for (int i = 0; i < len; i++) { KeyedValue tmp = contents.get(i); if (tmp.key.equals(key)) { return tmp.value; } } // for // Whoops! No keys matched throw new NoSuchKeyException("Could not find " + key.toString()); } // get(K) public class NoSuchKeyException extends Exception { public NoSuchKeyException(String reason) { super(reason); } } * put is O(1) in most cases Make a new key/value pair Shove it at the end Cross your fingers that the vector doesn't need to expand * The "Amortized" cost is O(1) public void put(K key, V value) { this.contents.add(new KeyedValue(key,value)); } How do we make this faster? * Divide and conquer