Section 16.7. Using the Set and Map Interfaces
16.7. Using the Set and Map InterfacesThe Set and Map interfaces are similar to the List interface in that there are multiple classes in the collections framework that implement them. 16.7.1. Using the Set InterfaceThe Set interface is modeled after the set theory principles taught in mathematics. In mathematics, sets are groups of elements with a clearly defined algorithm for deciding whether any given element is in any given set. Elements can be added to sets and removed from sets. Sets cannot have duplicate elements; if an element is added to a set that already contains an element equal to it, the new set still has a single such element. The elements of a set have no natural order; two sets that have the same elements listed in different orders are considered to be the same set. In computer science and in Java, data structures that model sets are designed for large collections of data. Such data structures have a method that determines whether an object is in a given set with an efficient algorithm. For large data sets, using such a method is much faster than iterating through a list. Whether you can list the elements of a set data structure in some natural order depends on how the data structure is implemented. An incomplete listing of the methods of the Set<E> interface is given in the UML diagram in Figure 16.32. Figure 16.32. A partial list of methods of the Set<E> interface. treeSet<E> and HashSet<E> are two classes in the collections framework that implement the Set<E> interface. They both provide fast operations to check whether an element is in a set. They also provide quick insertion of an element into the set or removal of an element from a set. For large setsthose with at least several thousand elementswhere there are large numbers of insertions, deletions, and tests for whether elements are in a set, linked lists would be much slower. When using the Set<E> interface for a user-defined class E, you will likely want to override the definition of the equals() method from the Object class in E because that method is used when computing the value of aSet.contains(anElement). When using the treeSet<E> class for a user-defined class E, you should implement the compareTo() method of the Comparable interface because it is used to order the elements of E. In the next section, we will discuss the specific manner in which elements are ordered. Finally, when using the HashSet<E> class for a user-defined class E, you should override the hashCode() method of the Object class because it is used in HashSet<E>. Hash codes are indexes computed from the particular object stored in the HashSet. Given an object's hash code, the object can be retrieved directly, as we do with objects stored in an array. However, we will not discuss hash codes in any detail in this text.
Overriding methods Problem StatementLet's think about a simple example for using a set data structure. Suppose that a programmer is developing an application for a large company for maintaining a no-call list. The programmer has decided to use the treeSet<E> data structure to store objects of the PhoneRecord class defined earlier in this chapter and will use methods of the Set<E> interface to manipulate the data. A TReeSet seems to be an appropriate structure for this problem because
The programmer might write a short method like the one in Figure 16.33 to demonstrate how the Set<E> and TReeSet<E> structures will be used. Figure 16.33. A method that demonstrates use of the interface Set<E> and the class TReeSet<E>. |
public static void testSet() { Set<PhoneRecord> theSet = new TreeSet<PhoneRecord>(); // new HashSet?phonerecord?(); could also be used. theSet.add(new PhoneRecord("Roger M", "090-997-2918")); theSet.add(new PhoneRecord("Jane M", "090-997-1987")); theSet.add(new PhoneRecord("Stacy K", "090-997-9188")); theSet.add(new PhoneRecord("Gary G", "201-119-8765")); theSet.add(new PhoneRecord("Jane M", "090-987-6543")); System.out.println("Testing TreeSet and Set"); PhoneRecord ph1 = new PhoneRecord("Roger M", "090-997-2918"); PhoneRecord ph2 = new PhoneRecord("Mary Q", "090-242-3344"); System.out.print("Roger M contained in theSet is "); System.out.println(theSet.contains(ph1)); System.out.print("Mary Q contained in theSet is "); System.out.println(theSet.contains(ph2)); for (PhoneRecord pr : theSet) System.out.println(pr); } // testSet() |
In order for the testSet() method to work as we would like, we need to have the PhoneRecord class implement the Comparable interface and override the equals() method. For this example, it is reasonable to assume that the name field of PhoneRecord objects should be unique so that it can be used to decide whether two PhoneRecord objects are equal. The name field of PhoneRecord can also be used to define the other two methods discussed above. Thus, add the following code to the PhoneRecord class.
public boolean equals(Object ob){ return name.equals(((PhoneRecord)ob).getName()); } // equals() public int compareTo(Object ob){ return name.compareTo(((PhoneRecord)ob).getName()); } // compareTo() public int hashCode(){ return name.hashCode(); } // hashCode()
The output of the TestSet() method is listed below:
Testing TreeSet and Set Roger M is contained in theSet is true Mary Q is contained in theSet is false Gary G 201-119-8765 Jane M 090-997-1987 Roger M 090-997-2918 Stacy K 090-997-9188
Note that Jane M PhoneRecord appears only once in the listing of elements in the set.
16.7.2. Using the Map<K,V> Interface
The Map<K,V> interface is modeled after looking up definitions for words in a dictionary. In computer science, maps are considered to be a collection of pairs of elements. A pair consists of a key that corresponds to a word being looked up, and a value corresponds to the definition of the word. Pairs can be added to maps and can be removed from maps. Maps cannot have distinct pairs with the same keys; if you attempt to add a pair to a map that already contains a pair with the same key, the second pair will replace the first. An incomplete listing of the methods of the Map<K,V> interface is given in the UML diagram in Figure 16.34. TReeMap<K,V> and HashMap<K,V> are two classes in the collections framework that implement the Map<K,V> interface.
Figure 16.34. A partial list of methods of Map<K,V>.
Let's now consider a simple example of using a map data structure. Suppose that our programmer has been hired by a large company to develop an application that maintains an electronic phone list for company employees. The programmer has decided to use the treeMap<E> data structure to store pairs of names and telephone numbers, and will use methods of the Map<V,K> interface to manipulate the data. A TReeMap seems like an appropriate data structure for this problem because
A large amount of data will be involved.
The company wants the PhoneRecord data stored in alphabetical order.
The main use of the data will be to use names to access telephone numbers.
The programmer might write a short method like the one in Figure 16.35 to demonstrate how the Map<K,V> and treeMap<K,V> structures will be used.
Figure 16.35. A method that demonstrates use of the interface Map<K,V> and the class TReeMap<K,V>.
public static void testMap() { Map<String, String> theMap = new TreeMap<String,String>(); // new HashMap<K,V>(); could also be used theMap.put("Roger M", "090-997-2918"); theMap.put("Jane M", "090-997-1987"); theMap.put("Stacy K", "090-997-9188"); theMap.put("Gary G", "201-119-8765"); theMap.put("Jane M", "090-233-0000"); System.out.println("Testing TreeMap and Map"); System.out.print("Stacy K has phone "); System.out.print(theMap.get("Stacy K"); System.out.print("Jane M has phone "); System.out.print(theMap.get("Jane M"); } // testMap() |
The output for this test program is:
Stacy K has phone 090-997-9188 Jane M has phone 090-233-0000
Note that the second phone number for Jane M is the one stored in the data structure.
EAN: 2147483647
Pages: 275