Activity 16.8.1.
Run the code below. Try adding a new PhoneRecord to the Set.
Section 16.8 Using the Set and Map Interfaces
The
Set and Map interfaces are similar to the List interface in that there are multiple classes in the collections framework that implement them.
Subsection 16.8.1 Using the Set Interface
The
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 if any given element is in any given set. Elements can be added to sets and can be 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 if 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. Sometimes, you may or may not be able to list the elements of a set data structure in some natural order, depending 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.8.1.
Set<E>.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 sets—those having at least several thousand elements—where 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 HashSet<E>. Hash codes are indexes that are computed from the particular object that is being stored in the HashSet. Given an object’s hash code, the object can be retrieved directly, as we do with object’s stored in an array. However, we will not discuss hash codes in any detail in this text.Subsection 16.8.2 Problem Statement
Let’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 that was 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, since 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 test whether names are in the set.The programmer might write a short method like that in Listing 16.8.2 to demonstrate how the
Set<E> and TreeSet<E> structures will be used.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
Set<E> and the class TreeSet<E>.In order for the
testSet() method to work as we would like, we need to have the PhoneRecord class implement the Comparable interface and to 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 if 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
Notice that
Jane MPhoneRecord appears only once in the listing of elements in the set.
Subsection 16.8.3 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 corresponding 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.8.3. TreeMap<K,V> and HashMap<K,V> are two classes in the collections framework that implement the Map<K,V> interface.
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, since 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 that in Listing 16.8.4 to demonstrate how the
Map<K,V> and TreeMap<K,V> structures will be used. Note that this code has been simplified to just store pairs of Strings, names and phone numbers, but it could be adapted to store names and PhoneRecords.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.println(theMap.get("Stacy K"));
System.out.print("Jane M has phone ");
System.out.println(theMap.get("Jane M"));
} // testMap
Map<K,V> and the class TreeMap<K,V>.Activity 16.8.2.
Run the code below. Try adding a new name and phone pair to the Map.
The output for this test program is:
Stacy K has phone 090-997-9188
Jane M has phone 090-233-0000
Notice the the second phone number for
Jane M is the one that is stored in the data structure.Exercises Self-Study Exercise
1.
Using the activity above as a guide, create a Map that translates words from English to another language.
Hint.
For example, you could put the pair cat and gato in the Map to translate cat into Spanish.
You have attempted of activities on this page.
