Sets and Maps

• The Set interface represents a Collection that does not allow duplicates
• A special kind of Set, given by the SortedSet interface, guarantees that the items are maintained in sorted order
• The unique operations required by the Set are the abilities to insert, remove, and perform a basic search (efficiently).
• For a Set, the add method returns true if the add succeeds and false if it fails because the item being added is already present.
• The implementation of Set that maintains items in sorted order is a TreeSet
• Basic operations in a TreeSet take logarithmic worst-case time.
• A Map is an interface that represents a collection of entries that consists of keys and their values.
• Keys must be unique, but several keys can map to the same values.
• In a SortedMap, the keys in the map are maintained in logically sorted order. An implementation of SortedMap is the TreeMap
• The basic operations for a Map include methods such as isEmpty, clear, size, get, put, and containsKey.
• get returns the value associated with key in the Map, or null if key is not present. If there are no null values in the Map, the value returned by get can be used to determine if key is in the Map. However, if there are null values, you have to use containsKey.
• Java requires that TreeSet and TreeMap support the basic add, remove, and contains operations in logarithmic worst-case time.
• By inserting elements into a search tree and then performing an inorder traversal, we obtain the elements in sorted order. This gives an O(N logN) algorithm to sort, which is a worst-case bound if any sophisticated search tree is used