Sets and MapsThe Set interfaceIterators for setsSet implementationsTypical set operationsSet equalityMembership testing in HashSetsThe SortedSet interfaceMembership testing in TreeSetsSet tipsThe Map interfaceMap implementationsMap: Basic operationsMore about putMap: Bulk operationsMap: Collection viewsMap.Entry: Interface for entrySet elementsThe EndSets and MapsPart of the Collections FrameworkThe Set interface•A Set is unordered and has no duplicates•Operations are exactly those for Collectionsint size( );boolean isEmpty( );boolean contains(Object e);boolean add(Object e); boolean remove(Object e); Iterator iterator( );boolean containsAll(Collection c);boolean addAll(Collection c); boolean removeAll(Collection c);boolean retainAll(Collection c);void clear( );Object[ ] toArray( );Object[ ] toArray(Object a[ ]);Iterators for sets•A set has a method Iterator iterator( ) to create an iterator over the set•The iterator has the usual methods:–boolean hasNext()–Object next()–void remove()•remove() allows you to remove elements as you iterate over the set•If you change the set in any other way during iteration, the iterator will throw a ConcurrentModificationExceptionSet implementations•Set is an interface; you can’t say new Set ( )•There are two implementations:–HashSet is best for most purposes–TreeSet guarantees the order of iteration•It’s poor style to expose the implementation, so:•Good: Set s = new HashSet( );Bad: HashSet s = new HashSet( );Typical set operations•Testing if s2 is a subset of s1 s1.containsAll(s2)•Setting s1 to the union of s1 and s2 s1.addAll(s2)•Setting s1 to the intersection of s1 and s2 s1.retainAll(s2)•Setting s1 to the set difference of s1 and s2 s1.removeAll(s2)Set equality•Object.equals(Object), inherited by all objects, really is an identity comparison•Implementations of Set override equals so that sets are equal if they contain the same elements•equals even works if two sets have different implementations•equals is a test on entire sets; you have to be sure you have a working equals on individual set elements•hashCode has been extended similarlyMembership testing in HashSets•When testing whether a HashSet contains a given object, Java does this:–Java computes the hash code for the given object•We’ll discuss hash codes later•Java compares the given object, using equals, only with elements in the set that have the same hash code•Hence, an object will be considered to be in the set only if both:–It has the same hash code as an element in the set, and–The equals comparison returns true•Moral: to use a HashSet properly, you must have a good public int hashCode() defined for the elements of the setThe SortedSet interface•A SortedSet is just like a Set, except that an Iterator will go through it in a guaranteed order•Implemented by TreeSetMembership testing in TreeSets•In a TreeSet, elements are kept in order•That means Java must have some means of comparing elements to decide which is “larger” and which is “smaller”•Java does this by using the int compareTo(Object) method of the Comparable interface•For this to work properly, compareTo must be consistent with equals•Moral: to use a TreeSet properly, you must implement both the equals method and the Comparable inteface for the elements of the setSet tips•add and remove return true if they modify the set•Here's a trick to remove duplicates from a Collection c:–Collection noDups = new HashSet(c); •A Set may not contain itself an an element•Danger: the behavior of a set is undefined if you change an element to be equal to another elementThe Map interface•A Map is an object that maps keys to values•A map cannot contain duplicate keys•Each key can map to at most one value•Examples: dictionary, phone book, etc.Map implementations•Map is an interface; you can’t say new Map ( )•Here are two implementations:–HashMap is the faster–TreeMap guarantees the order of iteration•It’s poor style to expose the implementation, so:•Good: Map map = new HashMap ( );Bad: HashMap map = new HashMap ( );Map: Basic operations Object put(Object key, Object value); Object get(Object key); Object remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size( ); boolean isEmpty( );More about put•If the map already contains a given key, put(key, value) replaces the value associated with that key•This means Java has to do equality testing on keys•With a HashMap implementation, you need to define equals and hashCode for all your keys•With a TreeMap implementation, you need to define equals and implement the Comparable interface for all your keysMap: Bulk operations•void putAll(Map t);–copies one Map into another•void clear();Map: Collection views•public Set keySet( );•public Collection values( );•public Set entrySet( );–returns a set of Map.Entry (key-value) pairs•You can create iterators for the key set, the value set, or the entry set•The above views provide the only way to iterate over a MapMap.Entry: Interface for entrySet elements •public interface Entry { Object getKey( ); Object getValue( ); Object setValue(Object value);}•This is a small interface for working with the Collection returned by entrySet( )•Can get elements only from the Iterator, and they are only valid during the iterationThe
View Full Document
Unlocking...