CSC152, Class 42: Vectors Admin * Visitors! * Homework: Finish and "write up" yesterday's lab for next Monday. * Quick quiz: What class number is it? Overview: * Vectors as ADT * Vectors as compound ADT * Questions * Lab /Questions on hashtables/ public class Silly { public int hashCode() { return 1; } // int hashCode() } public class LessSilly { String contents; public LessSilly(String _contents) { this.contents = _contents; } // LessSilly(String) public int hashCode() { // One strategy: Get the first character, get the UNICODE value, return it // Reminder: Java converts between primitive types when it can; // Each char can also be treated as an integer (which happens // to be its UNICODE v3 value) return this.contents.charAt(0); } // int hashCode() public String toString() { return this.contents; } // toString() public boolean equals(Object other) { return this.contents.equals(other.toString()); } // equals(Object) } // class LessSilly ht.put(new LessSilly("hello")); ht.put(new LessSilly("batman")); ht.put(new LessSilly("who")); ht.put(new LessSilly("is")); ht.put(new LessSilly("your")); ht.put(new LessSilly("partner")); ht.put(new LessSilly("today")); ht.dump(pen); With "first letter" a and q map to same cell in a size 16 b and r c and s d and t e and u f and v g and w h and x i and y BOOM /Vectors/ Three key aspects of each ADT * Purpose/Philosophy: A "growable" array of values. * Methods (our theory): * void put(int index, Object putMePlease) * Object get(int index) * size() * toString() or dump() * remove(int index) * Methods (Java practice): * put() might be expressed as add(Object), add(int index, Object addMe), and set(int index, Object setme) * get() might be expressed as get() or elementAt * capacity() or size() might work for size * toString() is there (it may or may not work) * remove() is there * Applications: Why would this be a useful ADT or DS? * We have lots of applications of arrays * We regularly write programs in which arrays need to grow. * Implementation: You've done it already with arrays Three key aspects of each ADT * Purpose/Philosophy: A "kitchen" sink of collections: You can do lots of different things. * Methods: * Set methods (contains) * List methods (visit values in sequence) * Dictionary-like methods (indexOf) * Applications * Even more! Sam's questions: * What's the difference between the capacity and the size? * size is how many things you've put in * capacity is how much total room there is * Example: If we create an array of size 10, but only use indices 0, 1, and 2: the capacity is 10, the size is 3 * When size is about to exceed capacity, you must expand! * Why do some basic ideas have two different methods to implement them? * E.g., get, elementAt (explicitly do the same thing) * Different interfaces we're implementing have chosen different names * Smarter designers might have ensured similar/identical naming in the interfaces * add and set * Subtle differences in meaning Lab!