Java Collections Framework - Building Java Programs: A Back to Basics Approach - page 691

Set Concepts
The two primary implementations of the Java Collections Framework's Set interface
are called HashSet and TreeSet . HashSet is the general-purpose set class, while
TreeSet offers a few advantages that will be discussed later. If you wanted to store a
set of String values, you could write code like the following:
Set<String> stooges = new HashSet<String>();
stooges.add("Larry");
stooges.add("Moe");
stooges.add("Curly");
stooges.add("Moe"); // duplicate, won't be added
stooges.add("Shemp");
stooges.add("Moe"); // duplicate, won't be added
After the code executes, the set will contain only four elements, because " Moe "
will be placed into the set only once. Notice that, as with lists, you can declare your
collection variable to be of the interface type rather than the class type (type Set
rather than type HashSet ).
A Set provides all of the operations from the Collection interface introduced
earlier in this chapter, such as add , contains , and remove . It's generally assumed
that the Set performs these operations efficiently, so you can add many elements to a
Set and search it many times without experiencing poor performance. A Set also
provides a toString method that lets you see its elements. Printing the preceding
stooges set would produce the following output:
[Moe, Shemp, Larry, Curly]
One of the most important benefits of using a Set such as HashSet is that it can
be searched incredibly quickly. Recall that the contains method of an ArrayList
or LinkedList must examine every element of the list in order until it finds the
target value. By contrast, the contains method of a HashSet is implemented in
such a way that it often needs to examine just one element, making it a much more
efficient operation.
A HashSet is implemented using a special internal array called a hash table that
places elements into specific positions based upon integers called hash codes. (Every
Java object has a hash code that can be accessed through its hashCode method.)
You don't need to understand the details of HashSet 's implementation to use it—the
bottom line is that it's implemented in such a way that you can add, remove, and
search for elements very quickly.
One drawback of HashSet is that it stores its elements in an unpredictable order.
The elements of the stooges set were not alphabetized, nor did they match the order
in which they were inserted. This storage practice is a tradeoff for the HashSet 's fast
performance. (Java now includes a variation called LinkedHashSet that is almost as
fast as HashSet but stores its elements in the order they were inserted.)