| |
Set functionality
Set has exactly the same interface as Collection, so there isn’t any extra functionality like there is with the two different Lists. Instead, the Set is exactly a Collection—it just has different behavior. (This is the ideal use of inheritance and polymorphism: to express different behavior.) A Set refuses to hold more than one instance of each object value (what constitutes the “value” of an object is more complex, as you shall see).
|
Set (interface)
|
Each element that you add to the Set must be unique; otherwise, the Set doesn’t add the duplicate element. Objects added to a Set must define equals( ) to establish object uniqueness. Set has exactly the same interface as Collection. The Set interface does not guarantee that it will maintain its elements in any particular order.
|
|
HashSet*
|
For Sets where fast lookup time is important. Objects must also define hashCode( ).
|
|
TreeSet
|
An ordered Set backed by a tree. This way, you can extract an ordered sequence from a Set.
|
|
LinkedHashSet
(JDK 1.4)
|
Has the lookup speed of a HashSet, but maintains the order in which you add the elements (the insertion order), internally using a linked list. Thus, when you iterate through the Set, the results appear in insertion order.
|
The following example does not show everything you can do with a Set, since the interface is the same as Collection, and so was exercised in the previous example. Instead, this demonstrates the behavior that makes a Set unique:
//: c11:Set1.java
// Things you can do with Sets.
import com.bruceeckel.simpletest.*;
import java.util.*;
public class Set1 {
private static Test monitor = new Test();
static void fill(Set s) {
s.addAll(Arrays.asList(
"one two three four five six seven".split(" ")));
}
public static void test(Set s) {
// Strip qualifiers from class name:
System.out.println(
s.getClass().getName().replaceAll("\\w+\\.", ""));
fill(s); fill(s); fill(s);
System.out.println(s); // No duplicates!
// Add another set to this one:
s.addAll(s);
s.add("one");
s.add("one");
s.add("one");
System.out.println(s);
// Look something up:
System.out.println("s.contains(\"one\"): " +
s.contains("one"));
}
public static void main(String[] args) {
test(new HashSet());
test(new TreeSet());
test(new LinkedHashSet());
monitor.expect(new String[] {
"HashSet",
"[one, two, five, four, three, seven, six]",
"[one, two, five, four, three, seven, six]",
"s.contains(\"one\"): true",
"TreeSet",
"[five, four, one, seven, six, three, two]",
"[five, four, one, seven, six, three, two]",
"s.contains(\"one\"): true",
"LinkedHashSet",
"[one, two, three, four, five, six, seven]",
"[one, two, three, four, five, six, seven]",
"s.contains(\"one\"): true"
});
}
} ///:~
Duplicate values are added to the Set, but when it is printed, you’ll see that the Set has accepted only one instance of each value.
When you run this program, you’ll notice that the order maintained by the HashSet is different from TreeSet and LinkedHashSet, since each has a different way of storing elements so they can be located later. (TreeSet keeps elements sorted into a red-black tree data structure, whereas HashSet uses a hashing function, which is designed specifically for rapid lookups. LinkedHashSet uses hashing internally for lookup speed, but appears to maintain elements in insertion order using a linked list.) When creating your own types, be aware that a Set needs a way to maintain a storage order, which means that you must implement the Comparable interface and define the compareTo( ) method. Here’s an example:
//: c11:Set2.java
// Putting your own type in a Set.
import com.bruceeckel.simpletest.*;
import java.util.*;
public class Set2 {
private static Test monitor = new Test();
public static Set fill(Set a, int size) {
for(int i = 0; i < size; i++)
a.add(new MyType(i));
return a;
}
public static void test(Set a) {
fill(a, 10);
fill(a, 10); // Try to add duplicates
fill(a, 10);
a.addAll(fill(new TreeSet(), 10));
System.out.println(a);
}
public static void main(String[] args) {
test(new HashSet());
test(new TreeSet());
test(new LinkedHashSet());
monitor.expect(new String[] {
"[2 , 4 , 9 , 8 , 6 , 1 , 3 , 7 , 5 , 0 ]",
"[9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 ]",
"[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]"
});
}
} ///:~
The form for the definitions for equals( ) and hashCode( ) will be described later in this chapter. You must define an equals( ) in both cases, but the hashCode( ) is absolutely necessary only if the class will be placed in a HashSet (which is likely, since that should generally be your first choice as a Set implementation). However, as a programming style, you should always override hashCode( ) when you override equals( ). This process will be fully detailed later in this chapter.
In the compareTo( ), note that I did not use the “simple and obvious” form return i-i2. Although this is a common programming error, it would only work properly if i and i2 were “unsigned” ints (if Java had an “unsigned” keyword, which it does not). It breaks for Java’s signed int, which is not big enough to represent the difference of two signed ints. If i is a large positive integer and j is a large negative integer, i-j will overflow and return a negative value, which will not work.
|
|
