Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·February 29, 2012 4:41:33 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E3.1 SYMBOL TABLES‣API‣sequential search‣binary search‣ordered operations2‣API‣sequential search‣binary search‣ordered operations3Symbol tablesKey-value pair abstraction.•Insert a value with specified key.•Given a key, search for the corresponding value.Ex. DNS lookup.•Insert URL with specified IP address.•Given URL, find corresponding IP address.keyURLIP addresswww.cs.princeton.edu128.112.136.11www.princeton.edu128.112.128.15www.yale.edu130.132.143.21www.harvard.edu128.103.060.55www.simpsons.com209.052.165.60value4Symbol table applicationsapplicationpurpose of searchkeyvaluedictionaryfind definitionworddefinitionbook indexfind relevant pagestermlist of page numbersfile sharefind song to downloadname of songcomputer IDfinancial accountprocess transactionsaccount numbertransaction detailsweb searchfind relevant web pageskeywordlist of page namescompilerfind properties of variablesvariable nametype and valuerouting tableroute Internet packetsdestinationbest routeDNSfind IP address given URLURLIP addressreverse DNSfind URL given IP addressIP addressURLgenomicsfind markersDNA stringknown positionsfile systemfind file on diskfilenamelocation on diskAssociative array abstraction. Associate one value with each key.API The symbol table is a prototypical abstract data type (see Chapter 1): it repre-sents a well-defined set of values and operations on those values, enabling us to develop clients and implementations separately. As usual, we precisely define the operations by specifying an applications programming interface (API) that provides the contract between client and implementation: public class ST<Key, Value>ST()create a symbol tablevoid put(Key key, Value val)put key-value pair into the table (remove key from table if value is null)Value get(Key key)value paired with key(null if key is absent)void delete(Key key)remove key (and its value) from tableboolean contains(Key key)is there a value paired with key?boolean isEmpty()is the table empty?int size()number of key-value pairs in the tableIterable<Key> keys()all the keys in the tableAPI for a generic basic symbol tableBefore examining client code, we consider several design choices for our implementa-tions to make our code consistent, compact, and useful. Generics. As we did with sorting, we will consider the methods without specifying the types of the items being processed, using generics. For symbol tables, we emphasize the separate roles played by keys and values in search by specifying the key and value types explicitly instead of viewing keys as implicit in items as we did for priority queues in Section 2.4. After we have considered some of the characteristics of this basic API (for example, note that there is no mention of order among the keys), we will consider an extension for the typical case when keys are Comparable, which enables numerous ad-ditional methods. Duplicate keys. We adopt the following conventions in all of our implementations:Only one value is associated with each key (no duplicate keys in a table).When a client puts a key-value pair into a table already containing that key (and an associated value), the new value replaces the old one. These conventions define the associative array abstraction, where you can think of a symbol table as being just like an array, where keys are indices and values are array 3633.1 Symbol Tables5Basic symbol table APIa[key] = val;a[key]6Conventions•Values are not null.•Method get() returns null if key not present.•Method put() overwrites old value with new value.Intended consequences.•Easy to implement contains().•Can implement lazy version of delete(). public boolean contains(Key key) { return get(key) != null; } public void delete(Key key) { put(key, null); }7Keys and valuesValue type. Any generic type.Key type: several natural assumptions.•Assume keys are Comparable, use compareTo().•Assume keys are any generic type, use equals() to test equality.•Assume keys are any generic type, use equals() to test equality;use hashCode() to scramble key.Best practices. Use immutable types for symbol table keys. •Immutable in Java: String, Integer, Double, java.io.File, …•Mutable in Java: StringBuilder, java.net.URL, arrays, ...specify Comparable in API.built-in to Java(stay tuned)8Equality testAll Java classes inherit a method equals(). Java requirements. For any references x, y and z:•Reflexive: x.equals(x) is true.•Symmetric: x.equals(y) iff y.equals(x).•Transitive: if x.equals(y) and y.equals(z), then x.equals(z).•Non-null: x.equals(null) is false.Default implementation. (x == y) Customized implementations. Integer, Double, String, File, URL, …User-defined implementations. Some care needed.do x and y refer tothe same object?equivalencerelationSeems easy.public class Date implements Comparable<Date>{ private final int month; private final int day; private final int year; ... public boolean equals(Date that) { if (this.day != that.day ) return false; if (this.month != that.month) return false; if (this.year != that.year ) return false; return true; }}Implementing equals for user-defined types9check that all significantfields are the sameSeems easy, but requires some care.public final class Date implements Comparable<Date>{ private final int month; private final int day; private final int year; ... public boolean equals(Object y) { if (y == this) return true; if (y == null) return false; if (y.getClass() != this.getClass()) return false; Date that = (Date) y; if (this.day != that.day ) return false; if (this.month != that.month) return false; if (this.year != that.year ) return false; return true; }}Implementing equals for user-defined types10check for nulloptimize for true object equalitytypically unsafe to use equals() with inheritance(would violate symmetry)must be Object.Why? Experts still debate.objects must be in the same class(religion: getClass() vs. instanceof)check that all significantfields are the samecast is guaranteed to succeed11Equals design"Standard" recipe for user-defined types.•Optimization for reference equality.•Check against null. •Check that two objects are of the
View Full Document
Unlocking...