Kĩ thuật lập trình - Lookup tables and hashing

Lookup Tables and HashingCopyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Learn about lookup tablesLearn about hashingReview java.util.HashSet and java.util.HashMap2Lookup TablesA lookup table is an array that helps to find data very quickly.The array stores references to data records (or some values).A data record is identified by some key.The value of a key is directly translated into an array index using a simple formula.3Lookup Tables (cont’d)Only one key can be mapped onto a particular index (no collisions).The index that corresponds to a key must fall into the valid range (from 0 to array.length-1).Access to data is “instantaneous” (O(1)). 4Lookup Tables: Example 1Zip codesCorresponding localesSome table entries remain unused5Lookup Tables: Example 2 private static final int [ ] n_thPowerOf3 = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683 }; ... // precondition: 0 and java.util.HashMap ClassesThese classes implement the Set and Map interfaces, respectively, using hash tables (with chaining).This implementation may be more efficient than TreeSet and TreeMap.13HashSet and HashMap (cont’d)Collisions are resolved through chaining.The sizes of buckets must remain relatively small.Load factor:Load factor = Total number of itemsNumber of buckets14HashSet and HashMap (cont’d)Fine tuning:Load factor too large  lots of collisionsLoad factor too small  wasted space and slow iterations over the whole setIf the load factor exceeds the specified limit, the table is automatically rehashed into a larger table; if possible this should be avoided.15HashSet and HashMap (cont’d)Objects in a HashSet or keys in a HashMap must have a reasonable int hashCode method that overrides Object’s hashCode and helps calculate the hashing function.The hashCode method returns an int from the entire int range; it is later mapped on the range of indices in a particular hash table.String, Integer, Double each have a reasonable hashCode defined.16hashCode ExamplesFor String:(where si is Unicode for the i-th character in the string)For Person:public int hashCode ( ) { return getFirstName( ).hashCode( ) + getLastName( ).hashCode( );}17ConsistencyHashSet / HashMap first use hashCode, then equals.TreeSet / TreeMap use only compareTo (or a comparator)For consistent performance, these methods should agree with each other:x.equals (y)  x.compareTo (y) == 0x.equals (y)  x.hashCode( ) == y.hashCode( )18HashSet ConstructorsNever mind...19HashMap Constructors20Review:What is the main difference between a lookup table and a hash table?What is a collision?Name two common techniques for resolving collisions.What is a bucket?What is a load factor?21Review (cont’d):How is hash table performance affected when the load factor is too high? Too low? What happens to a HashSet or a HashMap when the load factor exceeds the specified limit?HashSet’s no-args constructor sets the initial capacity to 16 and the load factor limit to 0.75. How many values can be stored in this table before it is rehashed?22Review (cont’d):What is the sequence of values returned by an iterator for a HashSet?What is the range of values for the hashCode method?Which method(s) of an object are used to find it in a TreeSet? A HashSet?23