Figure 9.1 A queue
The data structures that you choose can make a big difference when you try to implement methods in a natural style or are concerned with performance. Do you need to search quickly through thousands (or even millions) of sorted items? Do you need to rapidly insert and remove elements in the middle of an ordered sequence? Do you need to establish associations between keys and values?
This chapter shows how the Java library can help you accomplish the traditional data structuring needed for serious programming. In college computer science programs, a course called Data Structures usually takes a semester to complete, and there are many, many books devoted to this important topic. Our coverage differs from that of a college course; we will skip the theory and just show you how to use the collection classes in the standard library.
The initial release of Java supplied only a small set of classes for the most useful data structures: Vector, Stack, Hashtable, BitSet, and the Enumeration interface that provides an abstract mechanism for visiting elements in an arbitrary container. That was certainly a wise choice—it takes time and skill to come up with a comprehensive collection class library.
With the advent of Java SE 1.2, the designers felt that the time had come to roll out a full-fledged set of data structures. They faced a number of conflicting design challenges. They wanted the library to be small and easy to learn. They did not want the complexity of the Standard Template Library (or STL) of C++, but they wanted the benefit of “generic algorithms” that STL pioneered. They wanted the legacy classes to fit into the new framework. As all designers of collections libraries do, they had to make some hard choices, and they came up with a number of idiosyncratic design decisions along the way. In this section, we will explore the basic design of the Java collections framework, show you how to put it to work, and explain the reasoning behind some of the more controversial features.
As is common with modern data structure libraries, the Java collection library separates interfaces and implementations. Let us look at that separation with a familiar data structure, the queue.
A queue interface specifies that you can add elements at the tail end of the queue, remove them at the head, and find out how many elements are in the queue. You use a queue when you need to collect objects and retrieve them in a “first in, first out” fashion (see Figure 9.1).
A minimal form of a queue interface might look like this:
public interface Queue<E> // a simplified form of the interface in the standard library
{
void add(E element);
E remove();
int size();
}
The interface tells you nothing about how the queue is implemented. Of the two common implementations of a queue, one uses a “circular array” and one uses a linked list (see Figure 9.2).
Each implementation can be expressed by a class that implements the Queue interface.
public class CircularArrayQueue<E> implements Queue<E> // not an actual library class
{
private int head;
private int tail;
CircularArrayQueue(int capacity) { ... }
public void add(E element) { ... }
public E remove() { ... }
public int size() { ... }
private E[] elements;
}
public class LinkedListQueue<E> implements Queue<E> // not an actual library class
{
private Link head;
private Link tail;
LinkedListQueue() { ... }
public void add(E element) { ... }
public E remove() { ... }
public int size() { ... }
}
Note
The Java library doesn’t actually have classes named CircularArrayQueue and LinkedListQueue. We use these classes as examples to explain the conceptual distinction between collection interfaces and implementations. If you need a circular array queue, use the ArrayDeque class. For a linked list queue, simply use the LinkedList class—it implements the Queue interface.
When you use a queue in your program, you don’t need to know which implementation is actually used once the collection has been constructed. Therefore, it makes sense to use the concrete class only when you construct the collection object. Use the interface type to hold the collection reference.
Queue<Customer> expressLane = new CircularArrayQueue<>(100);
expressLane.add(new Customer("Harry"));
With this approach, if you change your mind, you can easily use a different implementation. You only need to change your program in one place—in the constructor call. If you decide that a LinkedListQueue is a better choice after all, your code becomes
Queue<Customer> expressLane = new LinkedListQueue<>();
expressLane.add(new Customer("Harry"));
Why would you choose one implementation over another? The interface says nothing about the efficiency of an implementation. A circular array is somewhat more efficient than a linked list, so it is generally preferable. However, as usual, there is a price to pay.
The circular array is a bounded collection—it has a finite capacity. If you don’t have an upper limit on the number of objects that your program will collect, you may be better off with a linked list implementation after all.
When you study the API documentation, you will find another set of classes whose name begins with Abstract, such as AbstractQueue. These classes are intended for library implementors. In the (perhaps unlikely) event that you want to implement your own queue class, you will find it easier to extend AbstractQueue than to implement all the methods of the Queue interface.
The fundamental interface for collection classes in the Java library is the Collection interface. The interface has two fundamental methods:
public interface Collection<E>
{
boolean add(E element);
Iterator<E> iterator();
...
}
There are several methods in addition to these two; we will discuss them later.
The add method adds an element to the collection. The add method returns true if adding the element actually changes the collection, and false if the collection is unchanged. For example, if you try to add an object to a set and the object is already present, the add request has no effect because sets reject duplicates.
The iterator method returns an object that implements the Iterator interface. You can use the iterator object to visit the elements in the collection one by one. We discuss iterators in the next section.
The Iterator interface has four methods:
public interface Iterator<E>
{
E next();
boolean hasNext();
void remove();
default void forEachRemaining(Consumer<? super E> action);
}
By repeatedly calling the next method, you can visit the elements from the collection one by one. However, if you reach the end of the collection, the next method throws a NoSuchElementException. Therefore, you need to call the hasNext method before calling next. That method returns true if the iterator object still has more elements to visit. If you want to inspect all elements in a collection, request an iterator and then keep calling the next method while hasNext returns true. For example:
Collection<String> c = ...;
Iterator<String> iter = c.iterator();
while (iter.hasNext())
{
String element = iter.next();
do something with element
}
You can write such a loop more concisely as the “for each” loop:
for (String element : c)
{
do something with element
}
The compiler simply translates the “for each” loop into a loop with an iterator.
The “for each” loop works with any object that implements the Iterable interface, an interface with a single abstract method:
public interface Iterable<E>
{
Iterator<E> iterator();
...
}
The Collection interface extends the Iterable interface. Therefore, you can use the “for each” loop with any collection in the standard library.
As of Java SE 8, you don’t even have to write a loop. You can call the forEachRemaining method with a lambda expression that consumes an element. The lambda expression is invoked with each element of the iterator, until there are none left.
iterator.forEachRemaining(element -> do something with element);
The order in which the elements are visited depends on the collection type. If you iterate over an ArrayList, the iterator starts at index 0 and increments the index in each step. However, if you visit the elements in a HashSet, you will get them in an essentially random order. You can be assured that you will encounter all elements of the collection during the course of the iteration, but you cannot make any assumptions about their ordering. This is usually not a problem because the ordering does not matter for computations such as computing totals or counting matches.
Old-timers will notice that the next and hasNext methods of the Iterator interface serve the same purpose as the nextElement and hasMoreElements methods of an Enumeration. The designers of the Java collections library could have chosen to make use of the Enumeration interface. But they disliked the cumbersome method names and instead introduced a new interface with shorter method names.
There is an important conceptual difference between iterators in the Java collections library and iterators in other libraries. In traditional collections libraries, such as the Standard Template Library of C++, iterators are modeled after array indexes. Given such an iterator, you can look up the element that is stored at that position, much like you can look up an array element a[i] if you have an array index i. Independently of the lookup, you can advance the iterator to the next position. This is the same operation as advancing an array index by calling i++, without performing a lookup. However, the Java iterators do not work like that. The lookup and position change are tightly coupled. The only way to look up an element is to call next, and that lookup advances the position.
Instead, think of Java iterators as being between elements. When you call next, the iterator jumps over the next element, and it returns a reference to the element that it just passed (see Figure 9.3).
Note
Here is another useful analogy. You can think of Iterator.next as the equivalent of InputStream.read. Reading a byte from a stream automatically “consumes” the byte. The next call to read consumes and returns the next byte from the input. Similarly, repeated calls to next let you read all elements in a collection.
The remove method of the Iterator interface removes the element that was returned by the last call to next. In many situations, that makes sense—you need to see the element before you can decide that it is the one that should be removed. But if you want to remove an element in a particular position, you still need to skip past the element. For example, here is how you remove the first element in a collection of strings:
Iterator<String> it = c.iterator();
it.next(); // skip over the first element
it.remove(); // now remove it
More importantly, there is a dependency between the calls to the next and remove methods. It is illegal to call remove if it wasn’t preceded by a call to next. If you try, an IllegalStateException is thrown.
If you want to remove two adjacent elements, you cannot simply call
it.remove();
it.remove(); // Error!
Instead, you must first call next to jump over the element to be removed.
it.remove();
it.next();
it.remove(); // OK
The Collection and Iterator interfaces are generic, which means you can write utility methods that operate on any kind of collection. For example, here is a generic method that tests whether an arbitrary collection contains a given element:
public static <E> boolean contains(Collection<E> c, Object obj)
{
for (E element : c)
if (element.equals(obj))
return true;
return false;
}
The designers of the Java library decided that some of these utility methods are so useful that the library should make them available. That way, library users don’t have to keep reinventing the wheel. The contains method is one such method.
In fact, the Collection interface declares quite a few useful methods that all implementing classes must supply. Among them are
int size()
boolean isEmpty()
boolean contains(Object obj)
boolean containsAll(Collection<?> c)
boolean equals(Object other)
boolean addAll(Collection<? extends E> from)
boolean remove(Object obj)
boolean removeAll(Collection<?> c)
void clear()
boolean retainAll(Collection<?> c)
Object[] toArray()
<T> T[] toArray(T[] arrayToFill)
Many of these methods are self-explanatory; you will find full documentation in the API notes at the end of this section.
Of course, it is a bother if every class that implements the Collection interface has to supply so many routine methods. To make life easier for implementors, the library supplies a class AbstractCollection that leaves the fundamental methods size and iterator abstract but implements the routine methods in terms of them. For example:
public abstract class AbstractCollection<E>
implements Collection<E>
{
...
public abstract Iterator<E> iterator();
public boolean contains(Object obj)
{
for (E element : this) // calls iterator()
if (element.equals(obj))
return = true;
return false;
}
...
}
A concrete collection class can now extend the AbstractCollection class. It is up to the concrete collection class to supply an iterator method, but the contains method has been taken care of by the AbstractCollection superclass. However, if the subclass has a more efficient way of implementing contains, it is free to do so.
With Java SE 8, this approach is a bit outdated. It would be nicer if the methods were default methods of the Collection interface. This has not happened. However, several default methods have been added. Most of them deal with streams (which we will discuss in Volume II). In addition, there is a useful method
default boolean removeIf(Predicate<? super E> filter)
for removing elements that fulfill a condition.
The Java collections framework defines a number of interfaces for different types of collections, shown in Figure 9.4.
There are two fundamental interfaces for collections: Collection and Map. As you already saw, you insert elements into a collection with a method
boolean add(E element)
However, maps hold key/value pairs, and you use the put method to insert them:
V put(K key, V value)
To read elements from a collection, visit them with an iterator. However, you can read values from a map with the get method:
V get(K key)
A List is an ordered collection. Elements are added into a particular position in the container. An element can be accessed in two ways: by an iterator or by an integer index. The latter is called random access because elements can be visited in any order. In contrast, when using an iterator, one must visit them sequentially.
The List interface defines several methods for random access:
void add(int index, E element)
void remove(int index)
E get(int index)
E set(int index, E element)
The ListIterator interface is a subinterface of Iterator. It defines a method for adding an element before the iterator position:
Frankly, this aspect of the collections framework is poorly designed. In practice, there are two kinds of ordered collections, with very different performance tradeoffs. An ordered collection that is backed by an array has fast random access, and it makes sense to use the List methods with an integer index. In contrast, a linked list, while also ordered, has slow random access, and it is best traversed with an iterator. It would have been an easy matter to provide two interfaces.
Note
To avoid carrying out random access operations for linked lists, Java SE 1.4 introduced a tagging interface, RandomAccess. That interface has no methods, but you can use it to test whether a particular collection supports efficient random access:
if (c instanceof RandomAccess)
{
use random access algorithm
}
else
{
use sequential access algorithm
}
The Set interface is identical to the Collection interface, but the behavior of the methods is more tightly defined. The add method of a set should reject duplicates. The equals method of a set should be defined so that two sets are identical if they have the same elements, but not necessarily in the same order. The hashCode method should be defined so that two sets with the same elements yield the same hash code.
Why make a separate interface if the method signatures are the same? Conceptually, not all collections are sets. Making a Set interface enables programmers to write methods that accept only sets.
The SortedSet and SortedMap interfaces expose the comparator object used for sorting, and they define methods to obtain views of subsets of the collections. We discuss these in Section 9.4, “Views and Wrappers,” on p. 509.
Finally, Java SE 6 introduced interfaces NavigableSet and NavigableMap that contain additional methods for searching and traversal in sorted sets and maps. (Ideally, these methods should have simply been included in the SortedSet and SortedMap interface.) The TreeSet and TreeMap classes implement these interfaces.
Table 9.1 shows the collections in the Java library and briefly describes the purpose of each collection class. (For simplicity, we omit the thread-safe collections that will be discussed in Chapter 14.) All classes in Table 9.1 implement the Collection interface, with the exception of the classes with names ending in Map. Those classes implement the Map interface instead. We will discuss maps in Section 9.3, “Maps,” on p. 497.
Figure 9.5 shows the relationships between these classes.
We already used arrays and their dynamic cousin, the ArrayList class, for many examples in this book. However, arrays and array lists suffer from a major drawback. Removing an element from the middle of an array is expensive since all array elements beyond the removed one must be moved toward the beginning of the array (see Figure 9.6). The same is true for inserting elements in the middle.
Another well-known data structure, the linked list, solves this problem. Where an array stores object references in consecutive memory locations, a linked list stores each object in a separate link. Each link also stores a reference to the next link in the sequence. In the Java programming language, all linked lists are actually doubly linked; that is, each link also stores a reference to its predecessor (see Figure 9.7).
Removing an element from the middle of a linked list is an inexpensive operation—only the links around the element to be removed need to be updated (see Figure 9.8).
Perhaps you once took a data structures course in which you learned how to implement linked lists. You may have bad memories of tangling up the links when removing or adding elements in the linked list. If so, you will be pleased to learn that the Java collections library supplies a class LinkedList ready for you to use.
The following code example adds three elements and then removes the second one:
List<String> staff = new LinkedList<>(); // LinkedList implements List
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
Iterator iter = staff.iterator();
String first = iter.next(); // visit first element
String second = iter.next(); // visit second element
iter.remove(); // remove last visited element
There is, however, an important difference between linked lists and generic collections. A linked list is an ordered collection in which the position of the objects matters. The LinkedList.add method adds the object to the end of the list. But you will often want to add objects somewhere in the middle of a list. This position-dependent add method is the responsibility of an iterator, since iterators describe positions in collections. Using iterators to add elements makes sense only for collections that have a natural ordering. For example, the set data type that we discuss in the next section does not impose any ordering on its elements. Therefore, there is no add method in the Iterator interface. Instead, the collections library supplies a subinterface ListIterator that contains an add method:
interface ListIterator<E> extends Iterator<E>
{
void add(E element);
. . .
}
Unlike Collection.add, this method does not return a boolean—it is assumed that the add operation always modifies the list.
In addition, the ListIterator interface has two methods that you can use for traversing a list backwards.
E previous()
boolean hasPrevious()
Like the next method, the previous method returns the object that it skipped over.
The listIterator method of the LinkedList class returns an iterator object that implements the ListIterator interface.
ListIterator<String> iter = staff.listIterator();
The add method adds the new element before the iterator position. For example, the following code skips past the first element in the linked list and adds "Juliet" before the second element (see Figure 9.9):
List<String> staff = new LinkedList<>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
ListIterator<String> iter = staff.listIterator();
iter.next(); // skip past first element
iter.add("Juliet");
If you call the add method multiple times, the elements are simply added in the order in which you supplied them. They are all added in turn before the current iterator position.
When you use the add operation with an iterator that was freshly returned from the listIterator method and that points to the beginning of the linked list, the newly added element becomes the new head of the list. When the iterator has passed the last element of the list (that is, when hasNext returns false), the added element becomes the new tail of the list. If the linked list has n elements, there are n + 1 spots for adding a new element. These spots correspond to the n + 1 possible positions of the iterator. For example, if a linked list contains three elements, A, B, and C, there are four possible positions (marked as |) for inserting a new element:
|ABC
A|BC
AB|C
ABC|
Note
Be careful with the “cursor” analogy. The remove operation does not work exactly like the Backspace key. Immediately after a call to next, the remove method indeed removes the element to the left of the iterator, just like the Backspace key would. However, if you have just called previous, the element to the right will be removed. And you can’t call remove twice in a row.
Unlike the add method, which depends only on the iterator position, the remove method depends on the iterator state.
Finally, a set method replaces the last element, returned by a call to next or previous, with a new element. For example, the following code replaces the first element of a list with a new value:
ListIterator<String> iter = list.listIterator();
String oldValue = iter.next(); // returns first element
iter.set(newValue); // sets first element to newValue
As you might imagine, if an iterator traverses a collection while another iterator is modifying it, confusing situations can occur. For example, suppose an iterator points before an element that another iterator has just removed. The iterator is now invalid and should no longer be used. The linked list iterators have been designed to detect such modifications. If an iterator finds that its collection has been modified by another iterator or by a method of the collection itself, it throws a ConcurrentModificationException. For example, consider the following code:
List<String> list = . . .;
ListIterator<String> iter1 = list.listIterator();
ListIterator<String> iter2 = list.listIterator();
iter1.next();
iter1.remove();
iter2.next(); // throws ConcurrentModificationException
The call to iter2.next throws a ConcurrentModificationException since iter2 detects that the list was modified externally.
To avoid concurrent modification exceptions, follow this simple rule: You can attach as many iterators to a collection as you like, provided that all of them are only readers. Alternatively, you can attach a single iterator that can both read and write.
Concurrent modification detection is done in a simple way. The collection keeps track of the number of mutating operations (such as adding and removing elements). Each iterator keeps a separate count of the number of mutating operations that it was responsible for. At the beginning of each iterator method, the iterator simply checks whether its own mutation count equals that of the collection. If not, it throws a ConcurrentModificationException.
Note
There is, however, a curious exception to the detection of concurrent modifications. The linked list only keeps track of structural modifications to the list, such as adding and removing links. The set method does not count as a structural modification. You can attach multiple iterators to a linked list, all of which call set to change the contents of existing links. This capability is required for a number of algorithms in the Collections class that we discuss later in this chapter.
Now you have seen the fundamental methods of the LinkedList class. Use a ListIterator to traverse the elements of the linked list in either direction and to add and remove elements.
As you saw in the preceding section, many other useful methods for operating on linked lists are declared in the Collection interface. These are, for the most part, implemented in the AbstractCollection superclass of the LinkedList class. For example, the toString method invokes toString on all elements and produces one long string of the format [A, B, C]. This is handy for debugging. Use the contains method to check whether an element is present in a linked list. For example, the call staff.contains("Harry") returns true if the linked list already contains a string equal to the string "Harry".
The library also supplies a number of methods that are, from a theoretical perspective, somewhat dubious. Linked lists do not support fast random access. If you want to see the nth element of a linked list, you have to start at the beginning and skip past the first n – 1 elements. There is no shortcut. For that reason, programmers don’t usually use linked lists in situations where elements need to be accessed by an integer index.
Nevertheless, the LinkedList class supplies a get method that lets you access a particular element:
LinkedList<String> list = ...;
String obj = list.get(n);
Of course, this method is not very efficient. If you find yourself using it, you are probably using a wrong data structure for your problem.
You should never use this illusory random access method to step through a linked list. The code
for (int i = 0; i < list.size(); i++)
do something with list.get(i);
is staggeringly inefficient. Each time you look up another element, the search starts again from the beginning of the list. The LinkedList object makes no effort to cache the position information.
Note
The get method has one slight optimization: If the index is at least size() / 2, the search for the element starts at the end of the list.
The list iterator interface also has a method to tell you the index of the current position. In fact, since Java iterators conceptually point between elements, it has two of them: The nextIndex method returns the integer index of the element that would be returned by the next call to next; the previousIndex method returns the index of the element that would be returned by the next call to previous. Of course, that is simply one less than nextIndex. These methods are efficient—an iterator keeps a count of its current position. Finally, if you have an integer index n, then list.listIterator(n) returns an iterator that points just before the element with index n. That is, calling next yields the same element as list.get(n); obtaining that iterator is inefficient.
If you have a linked list with only a handful of elements, you don’t have to be overly paranoid about the cost of the get and set methods. But then, why use a linked list in the first place? The only reason to use a linked list is to minimize the cost of insertion and removal in the middle of the list. If you have only a few elements, you can just use an ArrayList.
We recommend that you simply stay away from all methods that use an integer index to denote a position in a linked list. If you want random access into a collection, use an array or ArrayList, not a linked list.
The program in Listing 9.1 puts linked lists to work. It simply creates two lists, merges them, then removes every second element from the second list, and finally tests the removeAll method. We recommend that you trace the program flow and pay special attention to the iterators. You may find it helpful to draw diagrams of the iterator positions, like this:
|ACE |BDFG
A|CE |BDFG
AB|CE B|DFG
...
Note that the call
System.out.println(a);
prints all elements in the linked list a by invoking the toString method in AbstractCollection.
Listing 9.1 linkedList/LinkedListTest.java
1 package linkedList;
2
3 import java.util.*;
4
5 /**
6 * This program demonstrates operations on linked lists.
7 * @version 1.11 2012-01-26
8 * @author Cay Horstmann
9 */
10 public class LinkedListTest
11 {
12 public static void main(String[] args)
13 {
14 List<String> a = new LinkedList<>();
15 a.add("Amy");
16 a.add("Carl");
17 a.add("Erica");
18
19 List<String> b = new LinkedList<>();
20 b.add("Bob");
21 b.add("Doug");
22 b.add("Frances");
23 b.add("Gloria");
24
25 // merge the words from b into a
26
27 ListIterator<String> aIter = a.listIterator();
28 Iterator<String> bIter = b.iterator();
29
30 while (bIter.hasNext())
31 {
32 if (aIter.hasNext()) aIter.next();
33 aIter.add(bIter.next());
34 }
35
36 System.out.println(a);
37
38 // remove every second word from b
39
40 bIter = b.iterator();
41 while (bIter.hasNext())
42 {
43 bIter.next(); // skip one element
44 if (bIter.hasNext())
45 {
46 bIter.next(); // skip next element
47 bIter.remove(); // remove that element
48 }
49 }
50
51 System.out.println(b);
52
53 // bulk operation: remove all words in b from a
54
55 a.removeAll(b);
56
57 System.out.println(a);
58 }
59 }
In the preceding section, you saw the List interface and the LinkedList class that implements it. The List interface describes an ordered collection in which the position of elements matters. There are two protocols for visiting the elements: through an iterator and by random access with methods get and set. The latter is not appropriate for linked lists, but of course get and set make a lot of sense for arrays. The collections library supplies the familiar ArrayList class that also implements the List interface. An ArrayList encapsulates a dynamically reallocated array of objects.
Note
If you are a veteran Java programmer, you may have used the Vector class whenever you need a dynamic array. Why use an ArrayList instead of a Vector? For one simple reason: All methods of the Vector class are synchronized. It is safe to access a Vector object from two threads. But if you access a vector from only a single thread—by far the more common case—your code wastes quite a bit of time with synchronization. In contrast, the ArrayList methods are not synchronized. We recommend that you use an ArrayList instead of a Vector whenever you don’t need synchronization.
Linked lists and arrays let you specify the order in which you want to arrange the elements. However, if you are looking for a particular element and don’t remember its position, you need to visit all elements until you find a match. That can be time consuming if the collection contains many elements. If you don’t care about the ordering of the elements, there are data structures that let you find elements much faster. The drawback is that those data structures give you no control over the order in which the elements appear. These data structures organize the elements in an order that is convenient for their own purposes.
A well-known data structure for finding objects quickly is the hash table. A hash table computes an integer, called the hash code, for each object. A hash code is somehow derived from the instance fields of an object, preferably in such a way that objects with different data yield different codes. Table 9.2 lists a few examples of hash codes that result from the hashCode method of the String class.
If you define your own classes, you are responsible for implementing your own hashCode method—see Chapter 5 for more information. Your implementation needs to be compatible with the equals method: If a.equals(b), then a and b must have the same hash code.
What’s important for now is that hash codes can be computed quickly and that the computation depends only on the state of the object that needs to be hashed, not on the other objects in the hash table.
In Java, hash tables are implemented as arrays of linked lists. Each list is called a bucket (see Figure 9.10). To find the place of an object in the table, compute its hash code and reduce it modulo the total number of buckets. The resulting number is the index of the bucket that holds the element. For example, if an object has hash code 76268 and there are 128 buckets, then the object is placed in bucket 108 (because the remainder 76268 % 128 is 108). Perhaps you are lucky and there is no other element in that bucket. Then, you simply insert the element into that bucket. Of course, sometimes you will hit a bucket that is already filled. This is called a hash collision. Then, compare the new object with all objects in that bucket to see if it is already present. If the hash codes are reasonably randomly distributed and the number of buckets is large enough, only a few comparisons should be necessary.
Note
As of Java SE 8, the buckets change from linked lists into balanced binary trees when they get full. This improves performance if a hash function was poorly chosen and yields many collisions, or if malicious code tries to flood a hash table with many values that have identical hash codes.
If you want more control over the performance of the hash table, you can specify the initial bucket count. The bucket count gives the number of buckets used to collect objects with identical hash values. If too many elements are inserted into a hash table, the number of collisions increases and retrieval performance suffers.
If you know how many elements, approximately, will eventually be in the table, you can set the bucket count. Typically, you should set it to somewhere between 75% and 150% of the expected element count. Some researchers believe that it is a good idea to make the bucket count a prime number to prevent a clustering of keys. The evidence for this isn’t conclusive, however. The standard library uses bucket counts that are powers of 2, with a default of 16. (Any value you supply for the table size is automatically rounded to the next power of 2.)
Of course, you do not always know how many elements you need to store, or your initial guess may be too low. If the hash table gets too full, it needs to be rehashed. To rehash the table, a table with more buckets is created, all elements are inserted into the new table, and the original table is discarded. The load factor determines when a hash table is rehashed. For example, if the load factor is 0.75 (which is the default) and the table is more than 75% full, it is automatically rehashed with twice as many buckets. For most applications, it is reasonable to leave the load factor at 0.75.
Hash tables can be used to implement several important data structures. The simplest among them is the set type. A set is a collection of elements without duplicates. The add method of a set first tries to find the object to be added, and adds it only if it is not yet present.
The Java collections library supplies a HashSet class that implements a set based on a hash table. You add elements with the add method. The contains method is redefined to make a fast lookup to see if an element is already present in the set. It checks only the elements in one bucket and not all elements in the collection.
The hash set iterator visits all buckets in turn. Since hashing scatters the elements around in the table, they are visited in a seemingly random order. You would only use a HashSet if you don’t care about the ordering of the elements in the collection.
The sample program at the end of this section (Listing 9.2) reads words from System.in, adds them to a set, and finally prints out the first twenty words in the set. For example, you can feed the program the text from Alice in Wonderland (which you can obtain from www.gutenberg.org) by launching it from a command shell as
java SetTest < alice30.txt
The program reads all words from the input and adds them to the hash set. It then iterates through the unique words in the set and finally prints out a count. (Alice in Wonderland has 5,909 unique words, including the copyright notice at the beginning.) The words appear in random order.
Caution
Be careful when you mutate set elements. If the hash code of an element were to change, the element would no longer be in the correct position in the data structure.
1 package set;
2
3 import java.util.*;
4
5 /**
6 * This program uses a set to print all unique words in System.in.
7 * @version 1.12 2015-06-21
8 * @author Cay Horstmann
9 */
10 public class SetTest
11 {
12 public static void main(String[] args)
13 {
14 Set<String> words = new HashSet<>(); // HashSet implements Set
15 long totalTime = 0;
16
17 try (Scanner in = new Scanner(System.in))
18 {
19 while (in.hasNext())
20 {
21 String word = in.next();
22 long callTime = System.currentTimeMillis();
23 words.add(word);
24 callTime = System.currentTimeMillis() - callTime;
25 totalTime += callTime;
26 }
27 }
28
29 Iterator<String> iter = words.iterator();
30 for (int i = 1; i <= 20 && iter.hasNext(); i++)
31 System.out.println(iter.next());
32 System.out.println("...");
33 System.out.println(words.size() + " distinct words. " + totalTime + " milliseconds.");
34 }
35 }
The TreeSet class is similar to the hash set, with one added improvement. A tree set is a sorted collection. You insert elements into the collection in any order. When you iterate through the collection, the values are automatically presented in sorted order. For example, suppose you insert three strings and then visit all elements that you added.
SortedSet<String> sorter = new TreeSet<>(); // TreeSet implements SortedSet
sorter.add("Bob");
sorter.add("Amy");
sorter.add("Carl");
for (String s : sorter) System.println(s);
Then, the values are printed in sorted order: Amy Bob Carl. As the name of the class suggests, the sorting is accomplished by a tree data structure. (The current implementation uses a red-black tree. For a detailed description of red-black trees see, for example, Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, The MIT Press, 2009.) Every time an element is added to a tree, it is placed into its proper sorting position. Therefore, the iterator always visits the elements in sorted order.
Adding an element to a tree is slower than adding it to a hash table—see Table 9.3 for a comparison. But it is still much faster than checking for duplicates in an array or linked list. If the tree contains n elements, then an average of log2 n comparisons are required to find the correct position for the new element. For example, if the tree already contains 1,000 elements, adding a new element requires about 10 comparisons.
Note
In order to use a tree set, you must be able to compare the elements. The elements must implement the Comparable interface (see Section 6.1.1, “The Interface Concept,” on p. 288), or you must supply a Comparator when constructing the set (see Section 6.2.2, “The Comparator Interface,” on p. 305 and Section 6.3.8, “More about Comparators,” on p. 328).
If you look back at Table 9.3, you may well wonder if you should always use a tree set instead of a hash set. After all, adding elements does not seem to take much longer, and the elements are automatically sorted. The answer depends on the data that you are collecting. If you don’t need the data sorted, there is no reason to pay for the sorting overhead. More important, with some data it is much more difficult to come up with a sort order than a hash function. A hash function only needs to do a reasonably good job of scrambling the objects, whereas a comparison function must tell objects apart with complete precision.
To make this distinction more concrete, consider the task of collecting a set of rectangles. If you use a TreeSet, you need to supply a Comparator<Rectangle>. How do you compare two rectangles? By area? That doesn’t work. You can have two different rectangles with different coordinates but the same area. The sort order for a tree must be a total ordering. Any two elements must be comparable, and the comparison can only be zero if the elements are equal. There is such a sort order for rectangles (the lexicographic ordering on its coordinates), but it is unnatural and cumbersome to compute. In contrast, a hash function is already defined for the Rectangle class. It simply hashes the coordinates.
Note
As of Java SE 6, the TreeSet class implements the NavigableSet interface. That interface adds several convenient methods for locating elements and for backward traversal. See the API notes for details.
The program in Listing 9.3 builds two tree sets of Item objects. The first one is sorted by part number, the default sort order of Item objects. The second set is sorted by description, using a custom comparator.
Listing 9.3 treeSet/TreeSetTest.java
1 package treeSet;
2
3 import java.util.*;
4
5 /**
6 * This program sorts a set of item by comparing their descriptions.
7 * @version 1.12 2015-06-21
8 * @author Cay Horstmann
9 */
10 public class TreeSetTest
11 {
12 public static void main(String[] args)
13 {
14 SortedSet<Item> parts = new TreeSet<>();
15 parts.add(new Item("Toaster", 1234));
16 parts.add(new Item("Widget", 4562));
17 parts.add(new Item("Modem", 9912));
18 System.out.println(parts);
19
20 NavigableSet<Item> sortByDescription = new TreeSet<>(
21 Comparator.comparing(Item::getDescription));
22
23 sortByDescription.addAll(parts);
24 System.out.println(sortByDescription);
25 }
26 }
1 package treeSet;
2
3 import java.util.*;
4
5 /**
6 * An item with a description and a part number.
7 */
8 public class Item implements Comparable<Item>
9 {
10 private String description;
11 private int partNumber;
12
13 /**
14 * Constructs an item.
15 *
16 * @param aDescription
17 * the item's description
18 * @param aPartNumber
19 * the item's part number
20 */
21 public Item(String aDescription, int aPartNumber)
22 {
23 description = aDescription;
24 partNumber = aPartNumber;
25 }
26
27 /**
28 * Gets the description of this item.
29 *
30 * @return the description
31 */
32 public String getDescription()
33 {
34 return description;
35 }
36
37 public String toString()
38 {
39 return "[descripion=" + description + ", partNumber=" + partNumber + "]";
40 }
41
42 public boolean equals(Object otherObject)
43 {
44 if (this == otherObject) return true;
45 if (otherObject == null) return false;
46 if (getClass() != otherObject.getClass()) return false;
47 Item other = (Item) otherObject;
48 return Objects.equals(description, other.description) && partNumber == other.partNumber;
49 }
50
51 public int hashCode()
52 {
53 return Objects.hash(description, partNumber);
54 }
55
56 public int compareTo(Item other)
57 {
58 int diff = Integer.compare(partNumber, other.partNumber);
59 return diff != 0 ? diff : description.compareTo(other.description);
60 }
61 }
As we already discussed, a queue lets you efficiently add elements at the tail and remove elements from the head. A double-ended queue, or deque, lets you efficiently add or remove elements at the head and tail. Adding elements in the middle is not supported. Java SE 6 introduced a Deque interface. It is implemented by the ArrayDeque and LinkedList classes, both of which provide deques whose size grows as needed. In Chapter 14, you will see bounded queues and deques.
A priority queue retrieves elements in sorted order after they were inserted in arbitrary order. That is, whenever you call the remove method, you get the smallest element currently in the priority queue. However, the priority queue does not sort all its elements. If you iterate over the elements, they are not necessarily sorted. The priority queue makes use of an elegant and efficient data structure called a heap. A heap is a self-organizing binary tree in which the add and remove operations cause the smallest element to gravitate to the root, without wasting time on sorting all elements.
Just like a TreeSet, a priority queue can either hold elements of a class that implements the Comparable interface or a Comparator object you supply in the constructor.
A typical use for a priority queue is job scheduling. Each job has a priority. Jobs are added in random order. Whenever a new job can be started, the highest priority job is removed from the queue. (Since it is traditional for priority 1 to be the “highest” priority, the remove operation yields the minimum element.)
Listing 9.5 shows a priority queue in action. Unlike iteration in a TreeSet, the iteration here does not visit the elements in sorted order. However, removal always yields the smallest remaining element.
Listing 9.5 priorityQueue/PriorityQueueTest.java
1 package priorityQueue;
2
3 import java.util.*;
4 import java.time.*;
5
6 /**
7 * This program demonstrates the use of a priority queue.
8 * @version 1.01 2012-01-26
9 * @author Cay Horstmann
10 */
11 public class PriorityQueueTest
12 {
13 public static void main(String[] args)
14 {
15 PriorityQueue<LocalDate> pq = new PriorityQueue<>();
16 pq.add(LocalDate.of(1906, 12, 9)); // G. Hopper
17 pq.add(LocalDate.of(1815, 12, 10)); // A. Lovelace
18 pq.add(LocalDate.of(1903, 12, 3)); // J. von Neumann
19 pq.add(LocalDate.of(1910, 6, 22)); // K. Zuse
20
21 System.out.println("Iterating over elements...");
22 for (LocalDate date : pq)
23 System.out.println(date);
24 System.out.println("Removing elements...");
25 while (!pq.isEmpty())
26 System.out.println(pq.remove());
27 }
28 }
A set is a collection that lets you quickly find an existing element. However, to look up an element, you need to have an exact copy of the element to find. That isn’t a very common lookup—usually, you have some key information, and you want to look up the associated element. The map data structure serves that purpose. A map stores key/value pairs. You can find a value if you provide the key. For example, you may store a table of employee records, where the keys are the employee IDs and the values are Employee objects. In the following sections, you will learn how to work with maps.
The Java library supplies two general-purpose implementations for maps: HashMap and TreeMap. Both classes implement the Map interface.
A hash map hashes the keys, and a tree map uses an ordering on the keys to organize them in a search tree. The hash or comparison function is applied only to the keys. The values associated with the keys are not hashed or compared.
Should you choose a hash map or a tree map? As with sets, hashing is usually a bit faster, and it is the preferred choice if you don’t need to visit the keys in sorted order.
Here is how you set up a hash map for storing employees:
Map<String, Employee> staff = new HashMap<>(); // HashMap implements Map
Employee harry = new Employee("Harry Hacker");
staff.put("987-98-9996", harry);
...
Whenever you add an object to a map, you must supply a key as well. In our case, the key is a string, and the corresponding value is an Employee object.
To retrieve an object, you must use (and, therefore, remember) the key.
String id = "987-98-9996";
e = staff.get(id); // gets harry
If no information is stored in the map with the particular key specified, get returns null.
The null return value can be inconvenient. Sometimes, you have a good default that can be used for keys that are not present in the map. Then use the getOrDefault method.
Map<String, Integer> scores = ...;
int score = scores.get(id, 0); // Gets 0 if the id is not present
Keys must be unique. You cannot store two values with the same key. If you call the put method twice with the same key, the second value replaces the first one. In fact, put returns the previous value associated with its key parameter.
The remove method removes an element with a given key from the map. The size method returns the number of entries in the map.
The easiest way of iterating over the keys and values of a map is the forEach method. Provide a lambda expression that receives a key and a value. That expression is invoked for each map entry in turn.
scores.forEach((k, v) ->
System.out.println("key=" + k + ", value=" + v));
Listing 9.6 illustrates a map at work. We first add key/value pairs to a map. Then, we remove one key from the map, which removes its associated value as well. Next, we change the value that is associated with a key and call the get method to look up a value. Finally, we iterate through the entry set.
1 package map;
2
3 import java.util.*;
4
5 /**
6 * This program demonstrates the use of a map with key type String and value type Employee.
7 * @version 1.11 2012-01-26
8 * @author Cay Horstmann
9 */
10 public class MapTest
11 {
12 public static void main(String[] args)
13 {
14 Map<String, Employee> staff = new HashMap<>();
15 staff.put("144-25-5464", new Employee("Amy Lee"));
16 staff.put("567-24-2546", new Employee("Harry Hacker"));
17 staff.put("157-62-7935", new Employee("Gary Cooper"));
18 staff.put("456-62-5527", new Employee("Francesca Cruz"));
19
20 // print all entries
21
22 System.out.println(staff);
23
24 // remove an entry
25
26 staff.remove("567-24-2546");
27
28 // replace an entry
29
30 staff.put("456-62-5527", new Employee("Francesca Miller"));
31
32 // look up a value
33
34 System.out.println(staff.get("157-62-7935"));
35
36 // iterate through all entries
37
38 staff.forEach((k, v) ->
39 System.out.println("key=" + k + ", value=" + v));
40 }
41 }
A tricky part of dealing with maps is updating an entry. Normally, you get the old value associated with a key, update it, and put back the updated value. But you have to worry about the special case of the first occurrence of a key. Consider using a map for counting how often a word occurs in a file. When we see a word, we’d like to increment a counter like this:
counts.put(word, counts.get(word) + 1);
That works, except in the case when word is encountered for the first time. Then get returns null, and a NullPointerException occurs.
A simple remedy is to use the getOrDefault method:
counts.put(word, counts.getOrDefault(word, 0) + 1);
Another approach is to first call the putIfAbsent method. It only puts a value if the key was previously absent.
counts.putIfAbsent(word, 0);
counts.put(word, counts.get(word) + 1); // Now we know that get will succeed
But you can do better than that. The merge method simplifies this common operation. The call
counts.merge(word, 1, Integer::sum);
associates word with 1 if the key wasn’t previously present, and otherwise combines the previous value and 1, using the Integer::sum function.
The API notes describe other methods for updating map entries that are less commonly used.
The collections framework does not consider a map itself as a collection. (Other frameworks for data structures consider a map as a collection of key/value pairs, or as a collection of values indexed by the keys.) However, you can obtain views of the map—objects that implement the Collection interface or one of its subinterfaces.
There are three views: the set of keys, the collection of values (which is not a set), and the set of key/value pairs. The keys and key/value pairs form a set because there can be only one copy of a key in a map. The methods
Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K, V>> entrySet()
return these three views. (The elements of the entry set are objects of a class implementing the Map.Entry interface.)
Note that the keySet is not a HashSet or TreeSet, but an object of some other class that implements the Set interface. The Set interface extends the Collection interface. Therefore, you can use a keySet as you would use any collection.
For example, you can enumerate all keys of a map:
Set<String> keys = map.keySet();
for (String key : keys)
{
do something with key
}
If you want to look at both keys and values, you can avoid value lookups by enumerating the entries. Use the following code skeleton:
for (Map.Entry<String, Employee> entry : staff.entrySet())
{
String k = entry.getKey();
Employee v = entry.getValue();
do something with k, v
}
This used to be the most efficient way of visiting all map entries. Nowadays, simply use the forEach method:
counts.forEach((k, v) -> {
do something with k, v
});
If you invoke the remove method of the iterator on the key set view, you actually remove the key and its associated value from the map. However, you cannot add an element to the key set view. It makes no sense to add a key without also adding a value. If you try to invoke the add method, it throws an UnsupportedOperationException. The entry set view has the same restriction, even though it would make conceptual sense to add a new key/value pair.
The collection class library has several map classes for specialized needs that we briefly discuss in this and the following sections.
The WeakHashMap class was designed to solve an interesting problem. What happens with a value whose key is no longer used anywhere in your program? Suppose the last reference to a key has gone away. Then, there is no longer any way to refer to the value object. But, as no part of the program has the key any more, the key/value pair cannot be removed from the map. Why can’t the garbage collector remove it? Isn’t it the job of the garbage collector to remove unused objects?
Unfortunately, it isn’t quite so simple. The garbage collector traces live objects. As long as the map object is live, all buckets in it are live and won’t be reclaimed. Thus, your program should take care to remove unused values from long-lived maps. Or, you can use a WeakHashMap instead. This data structure cooperates with the garbage collector to remove key/value pairs when the only reference to the key is the one from the hash table entry.
Here are the inner workings of this mechanism. The WeakHashMap uses weak references to hold keys. A WeakReference object holds a reference to another object—in our case, a hash table key. Objects of this type are treated in a special way by the garbage collector. Normally, if the garbage collector finds that a particular object has no references to it, it simply reclaims the object. However, if the object is reachable only by a WeakReference, the garbage collector still reclaims the object, but places the weak reference that led to it into a queue. The operations of the WeakHashMap periodically check that queue for newly arrived weak references. The arrival of a weak reference in the queue signifies that the key was no longer used by anyone and has been collected. The WeakHashMap then removes the associated entry.
The LinkedHashSet and LinkedHashMap classes remember in which order you inserted items. That way, you can avoid the seemingly random order of items in a hash table. As entries are inserted into the table, they are joined in a doubly linked list (see Figure 9.11).
For example, consider the following map insertions from Listing 9.6:
Map<String, Employee> staff = new LinkedHashMap<>();
staff.put("144-25-5464", new Employee("Amy Lee"));
staff.put("567-24-2546", new Employee("Harry Hacker"));
staff.put("157-62-7935", new Employee("Gary Cooper"));
staff.put("456-62-5527", new Employee("Francesca Cruz"));
Then, staff.keySet().iterator() enumerates the keys in this order:
144-25-5464
567-24-2546
157-62-7935
456-62-5527
and staff.values().iterator() enumerates the values in this order:
Amy Lee
Harry Hacker
Gary Cooper
Francesca Cruz
A linked hash map can alternatively use access order, not insertion order, to iterate through the map entries. Every time you call get or put, the affected entry is removed from its current position and placed at the end of the linked list of entries. (Only the position in the linked list of entries is affected, not the hash table bucket. An entry always stays in the bucket that corresponds to the hash code of the key.) To construct such a hash map, call
LinkedHashMap<K, V>(initialCapacity, loadFactor, true)
Access order is useful for implementing a “least recently used” discipline for a cache. For example, you may want to keep frequently accessed entries in memory and read less frequently accessed objects from a database. When you don’t find an entry in the table, and the table is already pretty full, you can get an iterator into the table and remove the first few elements that it enumerates. Those entries were the least recently used ones.
You can even automate that process. Form a subclass of LinkedHashMap and override the method
protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
Adding a new entry then causes the eldest entry to be removed whenever your method returns true. For example, the following cache is kept at a size of at most 100 elements:
Map<K, V> cache = new
LinkedHashMap<>(128, 0.75F, true)
{
protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
{
return size() > 100;
}
}();
Alternatively, you can consider the eldest entry to decide whether to remove it. For example, you may want to check a time stamp stored with the entry.
The EnumSet is an efficient set implementation with elements that belong to an enumerated type. Since an enumerated type has a finite number of instances, the EnumSet is internally implemented simply as a sequence of bits. A bit is turned on if the corresponding value is present in the set.
The EnumSet class has no public constructors. Use a static factory method to construct the set:
enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);
You can use the usual methods of the Set interface to modify an EnumSet.
An EnumMap is a map with keys that belong to an enumerated type. It is simply and efficiently implemented as an array of values. You need to specify the key type in the constructor:
EnumMap<Weekday, Employee> personInCharge = new EnumMap<>(Weekday.class);
In the API documentation for EnumSet, you will see odd-looking type parameters of the form E extends Enum<E>. This simply means “E is an enumerated type.” All enumerated types extend the generic Enum class. For example, Weekday extends Enum<Weekday>.
The IdentityHashMap has a quite specialized purpose. Here, the hash values for the keys should not be computed by the hashCode method but by the System.identityHashCode method. That’s the method that Object.hashCode uses to compute a hash code from the object’s memory address. Also, for comparison of objects, the IdentityHashMap uses ==, not equals.
In other words, different key objects are considered distinct even if they have equal contents. This class is useful for implementing object traversal algorithms, such as object serialization, in which you want to keep track of which objects have already been traversed.
If you look at Figures 9.4 and 9.5, you might think it is overkill to have lots of interfaces and abstract classes to implement a modest number of concrete collection classes. However, these figures don’t tell the whole story. By using views, you can obtain other objects that implement the Collection or Map interfaces. You saw one example of this with the keySet method of the map classes. At first glance, it appears as if the method creates a new set, fills it with all the keys of the map, and returns it. However, that is not the case. Instead, the keySet method returns an object of a class that implements the Set interface and whose methods manipulate the original map. Such a collection is called a view.
The technique of views has a number of useful applications in the collections framework. We will discuss these applications in the following sections.
The static asList method of the Arrays class returns a List wrapper around a plain Java array. This method lets you pass the array to a method that expects a list or collection argument. For example:
Card[] cardDeck = new Card[52];
...
List<Card> cardList = Arrays.asList(cardDeck);
The returned object is not an ArrayList. It is a view object with get and set methods that access the underlying array. All methods that would change the size of the array (such as the add and remove methods of the associated iterator) throw an UnsupportedOperationException.
The asList method can receive a variable number of arguments. For example:
List<String> names = Arrays.asList("Amy", "Bob", "Carl");
The method call
Collections.nCopies(n, anObject)
returns an immutable object that implements the List interface and gives the illusion of having n elements, each of which appears as anObject.
For example, the following call creates a List containing 100 strings, all set to "DEFAULT":
List<String> settings = Collections.nCopies(100, "DEFAULT");
There is very little storage cost—the object is stored only once. This is a cute application of the view technique.
Note
The Collections class contains a number of utility methods with parameters or return values that are collections. Do not confuse it with the Collection interface.
The method call
Collections.singleton(anObject)
returns a view object that implements the Set interface (unlike nCopies, which produces a List). The returned object implements an immutable single-element set without the overhead of data structure. The methods singletonList and singletonMap behave similarly.
Similarly, there are methods that produce an empty set, list, map, and so on, for every interface in the collections framework. Impressively, the type of the set is inferred:
Set<String> deepThoughts = Collections.emptySet();
You can form subrange views for a number of collections. For example, suppose you have a list staff and want to extract elements 10 to 19. Use the subList method to obtain a view into the subrange of the list:
List group2 = staff.subList(10, 20);
The first index is inclusive, the second exclusive—just like the parameters for the substring operation of the String class.
You can apply any operations to the subrange, and they automatically reflect the entire list. For example, you can erase the entire subrange:
group2.clear(); // staff reduction
The elements get automatically cleared from the staff list, and group2 becomes empty.
For sorted sets and maps, you use the sort order, not the element position, to form subranges. The SortedSet interface declares three methods:
SortedSet<E> subSet(E from, E to)
SortedSet<E> headSet(E to)
SortedSet<E> tailSet(E from)
These return the subsets of all elements that are larger than or equal to from and strictly smaller than to. For sorted maps, the similar methods
SortedMap<K, V> subMap(K from, K to)
SortedMap<K, V> headMap(K to)
SortedMap<K, V> tailMap(K from)
return views into the maps consisting of all entries in which the keys fall into the specified ranges.
The NavigableSet interface introduced in Java SE 6 gives more control over these subrange operations. You can specify whether the bounds are included:
NavigableSet<E> subSet(E from, boolean fromInclusive, E to, boolean toInclusive)
NavigableSet<E> headSet(E to, boolean toInclusive)
NavigableSet<E> tailSet(E from, boolean fromInclusive)
The Collections class has methods that produce unmodifiable views of collections. These views add a runtime check to an existing collection. If an attempt to modify the collection is detected, an exception is thrown and the collection remains untouched.
You obtain unmodifiable views by eight methods:
Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableNavigableSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap
Collections.unmodifiableNavigableMap
Each method is defined to work on an interface. For example, Collections.unmodifiableList works with an ArrayList, a LinkedList, or any other class that implements the List interface.
For example, suppose you want to let some part of your code look at, but not touch, the contents of a collection. Here is what you could do:
List<String> staff = new LinkedList<>();
...
lookAt(Collections.unmodifiableList(staff));
The Collections.unmodifiableList method returns an object of a class implementing the List interface. Its accessor methods retrieve values from the staff collection. Of course, the lookAt method can call all methods of the List interface, not just the accessors. But all mutator methods (such as add) have been redefined to throw an UnsupportedOperationException instead of forwarding the call to the underlying collection.
The unmodifiable view does not make the collection itself immutable. You can still modify the collection through its original reference (staff, in our case). And you can still call mutator methods on the elements of the collection.
The views wrap the interface and not the actual collection object, so you only have access to those methods that are defined in the interface. For example, the LinkedList class has convenience methods, addFirst and addLast, that are not part of the List interface. These methods are not accessible through the unmodifiable view.
Caution
The unmodifiableCollection method (as well as the synchronizedCollection and checkedCollection methods discussed later in this section) returns a collection whose equals method does not invoke the equals method of the underlying collection. Instead, it inherits the equals method of the Object class, which just tests whether the objects are identical. If you turn a set or list into just a collection, you can no longer test for equal contents. The view acts in this way because equality testing is not well defined at this level of the hierarchy. The views treat the hashCode method in the same way.
However, the unmodifiableSet and unmodifiableList methods use the equals and hashCode methods of the underlying collections.
If you access a collection from multiple threads, you need to ensure that the collection is not accidentally damaged. For example, it would be disastrous if one thread tried to add to a hash table while another thread was rehashing the elements.
Instead of implementing thread-safe collection classes, the library designers used the view mechanism to make regular collections thread safe. For example, the static synchronizedMap method in the Collections class can turn any map into a Map with synchronized access methods:
Map<String, Employee> map = Collections.synchronizedMap(new HashMap<String, Employee>());
You can now access the map object from multiple threads. The methods such as get and put are serialized—each method call must be finished completely before another thread can call another method. We discuss the issue of synchronized access to data structures in greater detail in Chapter 14.
Checked views are intended as debugging support for a problem that can occur with generic types. As explained in Chapter 8, it is actually possible to smuggle elements of the wrong type into a generic collection. For example:
ArrayList<String> strings = new ArrayList<>();
ArrayList rawList = strings; // warning only, not an error, for compatibility with legacy code
rawList.add(new Date()); // now strings contains a Date object!
The erroneous add command is not detected at runtime. Instead, a class cast exception will happen later when another part of the code calls get and casts the result to a String.
A checked view can detect this problem. Define a safe list as follows:
List<String> safeStrings = Collections.checkedList(strings, String.class);
The view’s add method checks that the inserted object belongs to the given class and immediately throws a ClassCastException if it does not. The advantage is that the error is reported at the correct location:
ArrayList rawList = safeStrings;
rawList.add(new Date()); // checked list throws a ClassCastException
Caution
The checked views are limited by the runtime checks that the virtual machine can carry out. For example, if you have an ArrayList<Pair<String>>, you cannot protect it from inserting a Pair<Date> since the virtual machine has a single “raw” Pair class.
A view usually has some restriction—it may be read-only, it may not be able to change the size, or it may support removal but not insertion (as is the case for the key view of a map). A restricted view throws an UnsupportedOperationException if you attempt an inappropriate operation.
In the API documentation for the collection and iterator interfaces, many methods are described as “optional operations.” This seems to be in conflict with the notion of an interface. After all, isn’t the purpose of an interface to lay out the methods that a class must implement? Indeed, this arrangement is unsatisfactory from a theoretical perspective. A better solution might have been to design separate interfaces for read-only views and views that can’t change the size of a collection. However, that would have tripled the number of interfaces, which the designers of the library found unacceptable.
Should you extend the technique of “optional” methods to your own designs? We think not. Even though collections are used frequently, the coding style for implementing them is not typical for other problem domains. The designers of a collection class library have to resolve a particularly brutal set of conflicting requirements. Users want the library to be easy to learn, convenient to use, completely generic, idiot-proof, and at the same time as efficient as hand-coded algorithms. It is plainly impossible to achieve all these goals simultaneously, or even to come close. But in your own programming problems, you will rarely encounter such an extreme set of constraints. You should be able to find solutions that do not rely on the extreme measure of “optional” interface operations.
Generic collection interfaces have a great advantage—you only need to implement your algorithms once. For example, consider a simple algorithm to compute the maximum element in a collection. Traditionally, programmers would implement such an algorithm as a loop. Here is how you can find the largest element of an array.
if (a.length == 0) throw new NoSuchElementException();
T largest = a[0];
for (int i = 1; i < a.length; i++)
if (largest.compareTo(a[i]) < 0)
largest = a[i];
Of course, to find the maximum of an array list, you would write the code slightly differently.
if (v.size() == 0) throw new NoSuchElementException();
T largest = v.get(0);
for (int i = 1; i < v.size(); i++)
if (largest.compareTo(v.get(i)) < 0)
largest = v.get(i);
What about a linked list? You don’t have efficient random access in a linked list, but you can use an iterator.
if (l.isEmpty()) throw new NoSuchElementException();
Iterator<T> iter = l.iterator();
T largest = iter.next();
while (iter.hasNext())
{
T next = iter.next();
if (largest.compareTo(next) < 0)
largest = next;
}
These loops are tedious to write, and just a bit error-prone. Is there an off-by-one error? Do the loops work correctly for empty containers? For containers with only one element? You don’t want to test and debug this code every time, but you also don’t want to implement a whole slew of methods, such as these:
static <T extends Comparable> T max(T[] a)
static <T extends Comparable> T max(ArrayList<T> v)
static <T extends Comparable> T max(LinkedList<T> l)
That’s where the collection interfaces come in. Think of the minimal collection interface that you need to efficiently carry out the algorithm. Random access with get and set comes higher in the food chain than simple iteration. As you have seen in the computation of the maximum element in a linked list, random access is not required for this task. Computing the maximum can be done simply by iterating through the elements. Therefore, you can implement the max method to take any object that implements the Collection interface.
public static <T extends Comparable> T max(Collection<T> c)
{
if (c.isEmpty()) throw new NoSuchElementException();
Iterator<T> iter = c.iterator();
T largest = iter.next();
while (iter.hasNext())
{
T next = iter.next();
if (largest.compareTo(next) < 0)
largest = next;
}
return largest;
}
Now you can compute the maximum of a linked list, an array list, or an array, with a single method.
That’s a powerful concept. In fact, the standard C++ library has dozens of useful algorithms, each operating on a generic collection. The Java library is not quite so rich, but it does contain the basics: sorting, binary search, and some utility algorithms.
Computer old-timers will sometimes reminisce about how they had to use punched cards and to actually program, by hand, algorithms for sorting. Nowadays, of course, sorting algorithms are part of the standard library for most programming languages, and the Java programming language is no exception.
The sort method in the Collections class sorts a collection that implements the List interface.
List<String> staff = new LinkedList<>();
fill collection
Collections.sort(staff);
This method assumes that the list elements implement the Comparable interface. If you want to sort the list in some other way, you can use the sort method of the List interface and pass a Comparator object. Here is how you can sort a list of employees by salary:
staff.sort(Comparator.comparingDouble(Employee::getSalary));
If you want to sort a list in descending order, use the static convenience method Comparator.reverseOrder(). It returns a comparator that returns b.compareTo(a). For example,
staff.sort(Comparator.reverseOrder())
sorts the elements in the list staff in reverse order, according to the ordering given by the compareTo method of the element type. Similarly,
staff.sort(Comparator.comparingDouble(Employee::getSalary).reversed())
sorts by descending salary.
You may wonder how the sort method sorts a list. Typically, when you look at a sorting algorithm in a book on algorithms, it is presented for arrays and uses random element access. However, random access in a linked list is inefficient. You can actually sort linked lists efficiently by using a form of merge sort. However, the implementation in the Java programming language does not do that. It simply dumps all elements into an array, sorts the array, and then copies the sorted sequence back into the list.
The sort algorithm used in the collections library is a bit slower than QuickSort, the traditional choice for a general-purpose sorting algorithm. However, it has one major advantage: It is stable, that is, it doesn’t switch equal elements. Why do you care about the order of equal elements? Here is a common scenario. Suppose you have an employee list that you already sorted by name. Now you sort by salary. What happens to employees with equal salary? With a stable sort, the ordering by name is preserved. In other words, the outcome is a list that is sorted first by salary, then by name.
Collections need not implement all of their “optional” methods, so all methods that receive collection parameters must describe when it is safe to pass a collection to an algorithm. For example, you clearly cannot pass an unmodifiableList list to the sort algorithm. What kind of list can you pass? According to the documentation, the list must be modifiable but need not be resizable.
The terms are defined as follows:
• A list is modifiable if it supports the set method.
• A list is resizable if it supports the add and remove operations.
The Collections class has an algorithm shuffle that does the opposite of sorting—it randomly permutes the order of the elements in a list. For example:
ArrayList<Card> cards = . . .;
Collections.shuffle(cards);
If you supply a list that does not implement the RandomAccess interface, the shuffle method copies the elements into an array, shuffles the array, and copies the shuffled elements back into the list.
The program in Listing 9.7 fills an array list with 49 Integer objects containing the numbers 1 through 49. It then randomly shuffles the list and selects the first six values from the shuffled list. Finally, it sorts the selected values and prints them.
Listing 9.7 shuffle/ShuffleTest.java
1 package shuffle;
2
3 import java.util.*;
4
5 /**
6 * This program demonstrates the random shuffle and sort algorithms.
7 * @version 1.11 2012-01-26
8 * @author Cay Horstmann
9 */
10 public class ShuffleTest
11 {
12 public static void main(String[] args)
13 {
14 List<Integer> numbers = new ArrayList<>();
15 for (int i = 1; i <= 49; i++)
16 numbers.add(i);
17 Collections.shuffle(numbers);
18 List<Integer> winningCombination = numbers.subList(0, 6);
19 Collections.sort(winningCombination);
20 System.out.println(winningCombination);
21 }
22 }
To find an object in an array, you normally visit all elements until you find a match. However, if the array is sorted, you can look at the middle element and
check whether it is larger than the element that you are trying to find. If so, keep looking in the first half of the array; otherwise, look in the second half. That cuts the problem in half, and you keep going in the same way. For example, if the array has 1024 elements, you will locate the match (or confirm that there is none) after 10 steps, whereas a linear search would have taken you an average of 512 steps if the element is present, and 1024 steps to confirm that it is not.
The binarySearch of the Collections class implements this algorithm. Note that the collection must already be sorted, or the algorithm will return the wrong answer. To find an element, supply the collection (which must implement the List interface—more on that in the note below) and the element to be located. If the collection is not sorted by the compareTo element of the Comparable interface, supply a comparator object as well.
i = Collections.binarySearch(c, element);
i = Collections.binarySearch(c, element, comparator);
A non-negative return value from the binarySearch method denotes the index of the matching object. That is, c.get(i) is equal to element under the comparison order. If the value is negative, then there is no matching element. However, you can use the return value to compute the location where you should insert element into the collection to keep it sorted. The insertion location is
insertionPoint = -i - 1;
It isn’t simply -i because then the value of 0 would be ambiguous. In other words, the operation
if (i < 0)
c.add(-i - 1, element);
adds the element in the correct place.
To be worthwhile, binary search requires random access. If you have to iterate one by one through half of a linked list to find the middle element, you have lost all advantage of the binary search. Therefore, the binarySearch algorithm reverts to a linear search if you give it a linked list.
The Collections class contains several simple but useful algorithms. Among them is the example from the beginning of this section—finding the maximum value of a collection. Others include copying elements from one list to another, filling a container with a constant value, and reversing a list.
Why supply such simple algorithms in the standard library? Surely most programmers could easily implement them with simple loops. We like the algorithms because they make life easier for the programmer reading the code. When you read a loop that was implemented by someone else, you have to decipher the original programmer’s intentions. For example, look at this loop:
for (int i = 0; i < words.size(); i++)
if (words.get(i).equals("C++")) words.set(i, "Java");
Now compare the loop with the call
Collections.replaceAll("C++", "Java");
When you see the method call, you know right away what the code does.
The API notes at the end of this section describe the simple algorithms in the Collections class.
Java SE 8 adds default methods Collection.removeIf and List.replaceAll that are just a bit more complex. You provide a lambda expression to test or transform elements. For example, here we remove all short words and change the remaining ones to lowercase:
words.removeIf(w -> w.length() <= 3);
words.replaceAll(String::toLowerCase);
There are several operations that copy or remove elements “in bulk.” The call
coll1.removeAll(coll2);
removes all elements from coll1 that are present in coll2. Conversely,
coll1.retainAll(coll2);
removes all elements from coll1 that are not present in coll2. Here is a typical application.
Suppose you want to find the intersection of two sets—the elements that two sets have in common. First, make a new set to hold the result.
Set<String> result = new HashSet<>(a);
Here, we use the fact that every collection has a constructor whose parameter is another collection that holds the initialization values.
Now, use the retainAll method:
result.retainAll(b);
It retains all elements that also happen to be in b. You have formed the intersection without programming a loop.
You can carry this idea further and apply a bulk operation to a view. For example, suppose you have a map that maps employee IDs to employee objects and you have a set of the IDs of all employees that are to be terminated.
Map<String, Employee> staffMap = . . .;
Set<String> terminatedIDs = . . .;
Simply form the key set and remove all IDs of terminated employees.
staffMap.keySet().removeAll(terminatedIDs);
Since the key set is a view into the map, the keys and associated employee names are automatically removed from the map.
By using a subrange view, you can restrict bulk operations to sublists and subsets. For example, suppose you want to add the first ten elements of a list to another container. Form a sublist to pick out the first ten:
relocated.addAll(staff.subList(0, 10));
The subrange can also be a target of a mutating operation.
staff.subList(0, 10).clear();
Large portions of the Java platform API were designed before the collections framework was created. As a result, you will occasionally need to translate between traditional arrays and the more modern collections.
If you have an array that you need to turn into a collection, the Arrays.asList wrapper serves this purpose. For example:
String[] values = ...;
HashSet<String> staff = new HashSet<>(Arrays.asList(values));
Obtaining an array from a collection is a bit trickier. Of course, you can use the toArray method:
Object[] values = staff.toArray();
But the result is an array of objects. Even if you know that your collection contained objects of a specific type, you cannot use a cast:
String[] values = (String[]) staff.toArray(); // Error!
The array returned by the toArray method was created as an Object[] array, and you cannot change its type. Instead, use a variant of the toArray method and give it an array of length 0 of the type that you’d like. The returned array is then created as the same array type:
String[] values = staff.toArray(new String[0]);
If you like, you can construct the array to have the correct size:
staff.toArray(new String[staff.size()]);
In this case, no new array is created.
Note
You may wonder why you can’t simply pass a Class object (such as String.class) to the toArray method. However, this method does “double duty”—both to fill an existing array (provided it is long enough) and to create a new array.
If you write your own algorithm (or, in fact, any method that has a collection as a parameter), you should work with interfaces, not concrete implementations, whenever possible. For example, suppose you want to fill a JMenu with a set of menu items. Traditionally, such a method might have been implemented like this:
void fillMenu(JMenu menu, ArrayList<JMenuItem> items)
{
for (JMenuItem item : items)
menu.add(item);
}
However, you now constrained the caller of your method—the caller must supply the choices in an ArrayList. If the choices happen to be in another container, they first need to be repackaged. It is much better to accept a more general collection.
You should ask yourself this: What is the most general collection interface that can do the job? In this case, you just need to visit all elements, a capability of the basic Collection interface. Here is how you can rewrite the fillMenu method to accept collections of any kind:
void fillMenu(JMenu menu, Collection<JMenuItem> items)
{
for (JMenuItem item : items)
menu.add(item);
}
Now, anyone can call this method with an ArrayList or a LinkedList, or even with an array wrapped with the Arrays.asList wrapper.
Note
If it is such a good idea to use collection interfaces as method parameters, why doesn’t the Java library follow this rule more often? For example, the JComboBox class has two constructors:
JComboBox(Object[] items)
JComboBox(Vector<?> items)
The reason is simply timing. The Swing library was created before the collections library.
If you write a method that returns a collection, you may also want to return an interface instead of a class because you can then change your mind and reimplement the method later with a different collection.
For example, let’s write a method getAllItems that returns all items of a menu.
List<JMenuItem> getAllItems(JMenu menu)
{
List<JMenuItem> items = new ArrayList<>()
for (int i = 0; i < menu.getItemCount(); i++)
items.add(menu.getItem(i));
return items;
}
Later, you may decide that you don’t want to copy the items but simply provide a view into them. You can achieve this by returning an anonymous subclass of AbstractList.
List<JMenuItem> getAllItems(final JMenu menu)
{
return new
AbstractList<>()
{
public JMenuItem get(int i)
{
return menu.getItem(i);
}
public int size()
{
return menu.getItemCount();
}
};
}
Of course, this is an advanced technique. If you employ it, be careful to document exactly which “optional” operations are supported. In this case, you must advise the caller that the returned object is an unmodifiable list.
A number of “legacy” container classes have been present since the first release of Java, before there was a collections framework.
They have been integrated into the collections framework—see Figure 9.12. We briefly introduce them in the following sections.
The classic Hashtable class serves the same purpose as the HashMap class and has essentially the same interface. Just like methods of the Vector class, the Hashtable methods are synchronized. If you do not require compatibility with legacy code, you should use a HashMap instead. If you need concurrent access, use a ConcurrentHashMap—see Chapter 14.
The legacy collections use the Enumeration interface for traversing sequences of elements. The Enumeration interface has two methods, hasMoreElements and nextElement. These are entirely analogous to the hasNext and next methods of the Iterator interface.
For example, the elements method of the Hashtable class yields an object for enumerating the values in the table:
Enumeration<Employee> e = staff.elements();
while (e.hasMoreElements())
{
Employee e = e.nextElement();
...
}
You will occasionally encounter a legacy method that expects an enumeration parameter. The static method Collections.enumeration yields an enumeration object that enumerates the elements in the collection. For example:
List<InputStream> streams = ...;
SequenceInputStream in = new SequenceInputStream(Collections.enumeration(streams));
// the SequenceInputStream constructor expects an enumeration
In C++, it is quite common to use iterators as parameters. Fortunately, on the Java platform, very few programmers use this idiom. It is much smarter to pass around the collection than to pass an iterator. The collection object is more useful. The recipients can always obtain the iterator from the collection when they need to do so, plus they have all the collection methods at their disposal. However, you will find enumerations in some legacy code because they were the only available mechanism for generic collections until the collections framework appeared in Java SE 1.2.
A property map is a map structure of a very special type. It has three particular characteristics:
• The keys and values are strings.
• The table can be saved to a file and loaded from a file.
• A secondary table for defaults is used.
The Java platform class that implements a property map is called Properties.
Property maps are commonly used in specifying configuration options for programs—see Chapter 13.
Since version 1.0, the standard library had a Stack class with the familiar push and pop methods. However, the Stack class extends the Vector class, which is not satisfactory from a theoretical perspective—you can apply such un-stack-like operations as insert and remove to insert and remove values anywhere, not just at the top of the stack.
The Java platform’s BitSet class stores a sequence of bits. (It is not a set in the mathematical sense—bit vector or bit array would have been more appropriate terms.) Use a bit set if you need to store a sequence of bits (for example, flags) efficiently. A bit set packs the bits into bytes, so it is far more efficient to use a bit set than an ArrayList of Boolean objects.
The BitSet class gives you a convenient interface for reading, setting, and resetting individual bits. Using this interface avoids the masking and other bit-fiddling operations that are necessary if you store bits in int or long variables.
For example, for a BitSet named bucketOfBits,
bucketOfBits.get(i)
returns true if the ith bit is on, and false otherwise. Similarly,
bucketOfBits.set(i)
turns the ith bit on. Finally,
bucketOfBits.clear(i)
turns the ith bit off.
C++ Note
The C++ bitset template has the same functionality as the Java platform BitSet.
As an example of using bit sets, we want to show you an implementation of the “sieve of Eratosthenes” algorithm for finding prime numbers. (A prime number is a number like 2, 3, or 5 that is divisible only by itself and 1, and the sieve of Eratosthenes was one of the first methods discovered to enumerate these fundamental building blocks.) This isn’t a terribly good algorithm for finding the primes, but for some reason it has become a popular benchmark for compiler performance. (It isn’t a good benchmark either, because it mainly tests bit operations.)
Oh well, we bow to tradition and present an implementation. This program counts all prime numbers between 2 and 2,000,000. (There are 148,933 primes in this interval, so you probably don’t want to print them all out.)
Without going into too many details of this program, the idea is to march through a bit set with 2 million bits. First, we turn on all the bits. After that, we turn off the bits that are multiples of numbers known to be prime. The positions of the bits that remain after this process are themselves prime numbers. Listing 9.8 lists this program in the Java programming language, and Listing 9.9 is the C++ code.
Note
Even though the sieve isn’t a good benchmark, we couldn’t resist timing the two implementations of the algorithm. Here are the timing results on a 2.9-GHz dual core ThinkPad with 8 GB of RAM, running Ubuntu 14.04.
• C++ (g++ 4.6.3): 390 milliseconds
• Java (Java SE 8): 119 milliseconds
We have run this test for nine editions of Core Java, and in the last five editions, Java easily beat C++. In all fairness, if one cranks up the optimization level in the C++ compiler, it beats Java with a time of 33 milliseconds. Java could only match that if the program ran long enough to trigger the Hotspot just-in-time compiler.
1 package sieve;
2
3 import java.util.*;
4
5 /**
6 * This program runs the Sieve of Erathostenes benchmark. It computes all primes up to 2,000,000.
7 * @version 1.21 2004-08-03
8 * @author Cay Horstmann
9 */
10 public class Sieve
11 {
12 public static void main(String[] s)
13 {
14 int n = 2000000;
15 long start = System.currentTimeMillis();
16 BitSet b = new BitSet(n + 1);
17 int count = 0;
18 int i;
19 for (i = 2; i <= n; i++)
20 b.set(i);
21 i = 2;
22 while (i * i <= n)
23 {
24 if (b.get(i))
25 {
26 count++;
27 int k = 2 * i;
28 while (k <= n)
29 {
30 b.clear(k);
31 k += i;
32 }
33 }
34 i++;
35 }
36 while (i <= n)
37 {
38 if (b.get(i)) count++;
39 i++;
40 }
41 long end = System.currentTimeMillis();
42 System.out.println(count + " primes");
43 System.out.println((end - start) + " milliseconds");
44 }
45 }
1 /**
2 @version 1.21 2004-08-03
3 @author Cay Horstmann
4 */
5
6 #include <bitset>
7 #include <iostream>
8 #include <ctime>
9
10 using namespace std;
11
12 int main()
13 {
14 const int N = 2000000;
15 clock_t cstart = clock();
16
17 bitset<N + 1> b;
18 int count = 0;
19 int i;
20 for (i = 2; i <= N; i++)
21 b.set(i);
22 i = 2;
23 while (i * i <= N)
24 {
25 if (b.test(i))
26 {
27 count++;
28 int k = 2 * i;
29 while (k <= N)
30 {
31 b.reset(k);
32 k += i;
33 }
34 }
35 i++;
36 }
37 while (i <= N)
38 {
39 if (b.test(i))
40 count++;
41 i++;
42 }
43
44 clock_t cend = clock();
45 double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;
46
47 cout << count << " primes\n" << millis << " milliseconds\n";
48
49 return 0;
50 }
This completes our tour through the Java collections framework. As you have seen, the Java library offers a wide variety of collection classes for your programming needs. In the next chapter, you will learn how to write graphical user interfaces.
