APPENDIX 1

Additional Features of the JAVA Collections Framework

A1.1 Introduction

The Java Collections Framework has several features beyond those encountered so far in this book. This appendix focuses on two of those features: serialization and fail-fast iterators.

A1.2 Serialization

Suppose we have gone to the trouble of creating a large and complex HashMap object as part of a project. After we have used that HashMap object in an execution of the project, we might want to save the HashMap, on file, so that we can later resume the execution of the project without having to re-construct the HashMap. Fortunately, this is easily done with just a couple of statements.

How? All of the collection classes in the Java Collections Framework implement the Serializable interface that is in the package java.io. This interface has no methods, but merely provides information to the Java virtual machine about sending instances of the class to/from a stream (a sequence of bytes). Specifically, any class that implements the Serializable interface will be able to copy any object in the class to an output stream—that is, to "serialize" the elements in the object. "Deserialization" reconstructs the original object from an input stream.

For a simple example, suppose we have created an ArrayList object named fruits, whose elements are of type string. We can create an Objectoutputstream and then write fruits to the FileOutputstream object whose path is "fruits.ser" as follows:

try
{
     ObjectOutputStream oos = new ObjectOutputStream (
                                new FileOutputStream ("fruits.ser"));
     oos.writeObject (fruits);
} // try
catch (IOException e)
{
     System.out.println (e);
} // catch

The ArrayList object fruits has been serialized, that is, is saved as a stream of bytes. The file qualifier, "ser", is an abbreviation of "serializable," but you are free to use any qualifier you want, or no qualifier. The definition of the writeObject method depends on the class of the object serialized. For example, here is the definition in the ArrayList class:

try
{
     ObjectOutputStream oos = new ObjectOutputStream (
                                new FileOutputStream ("fruits.ser"));
     oos.writeObject (fruits);
} // try
catch (IOException e)
{
     System.out.println (e);
} // catch

 * The worstTime(n) is O(n).
 *
 * @serialData The length of the array backing the <tt>ArrayList</tt>
 *         instance is emitted (int), followed by all of its elements
 *         (each an <tt>Object</tt>) in the proper order.
 */
private void writeObject (java.io.ObjectOutputStream s)
             throws java.io.IOException
{
       // Write out element count, and any hidden stuff
       s.defaultWriteObject();


       // Write out array length
       s.writeInt (elementData.length);


       // Write out all elements in the proper order.
       for (int i=0; i<size; i++)
            s.writeObject (elementData [i]);
}

The size of the ArrayList object is saved first, and then the length of the elementData array field, so that an array of the exact same capacity can be created when the ArrayList object is reconstructed from the file. Finally, the elements in the ArrayList object are saved to the file.

In another program, or in a later execution of the same program, we can de-serialize fruits. To accomplish that task, we create an ObjectInputStream object to read the stream of bytes, from the FileInputStream whose path is "fruits.ser", into fruits:

try
{
       ObjectInputStream ois = new ObjectInputStream (
                                 new FileInputStream ("fruits.ser"));
       fruits = (ArrayList<String>)ois.readObject ();
} // try
catch (Exception e)
{
       System.out.println (e);
} // catch

In the readObject method, the first value read from the stream represents the size of the ArrayList object, and the next value represents the length of the underlying array, and finally, the individual elements are read, one at a time.

An object that is saved and then retrieved in another program (or later execution of the same program) is called persistent. In this example, the ArrayList object fruits is persistent. And the same mechanism shown above can be used to create persistent instances of any of the other collection classes in the Java Collections Framework.

You can make your own classes serializable. Right after the class heading, add

implements java.io.Serializable;

If all that have to be saved are fields, you needn't define writeObject and readObject methods: the default serialization/deserialization will handle fields. In the ArrayList example just listed, the defaults were not enough; the length of the array elementData and the elements themselves had to be saved. That is why the ArrayList class explicitly defines writeObject and readObject methods.

A1.3 Fail-Fast Iterators

Once an iterator has started iterating over a collection, that collection should not be structurally modified except by that iterator. A structural modification is either an insertion or removal; accessors and mutators do not structurally modify a collection. First, we'll see how this prohibition against structural modification can be helpful to users, and then we'll look at how the prohibition is enforced in the Java Collections Framework.

The following main method creates a small LinkedList object. During an iteration over that object, the object modifies itself, and then the iteration continues.

public static void main (String[ ] args)
{
      LinkedList<String> list = new LinkedList<String>();


      list.add ("humble");
      list.add ("meek");
      list.add ("modest");


      Iterator<String> itr = list.iterator();
      System.out.println (itr.next());   // prints "humble"
      list.remove ("modest");
      System.out.println (itr.next());   // prints "meek"?
      System.out.println (itr.next());   // ???
} // method main

The program constructs a LinkedList object, list, of three elements. An iterator, itr, starts iterating over list. When itr calls its next() method, the element "humble" at index 0 is returned, and itr advances to index 1. At this point, list removes the element at index 2. The second call to the next() method should be flagged as illegal. Why? The element "meek" at index 1 could be returned, but itr should not be allowed to advance to and print the element at index 2 because there is no longer an element at index 2. So what is best for the programmer is to have the error detected when the second call to the next() method is made, rather than having the error detected later in the program.

And that is exactly what happens. When this program was run, the value "humble" was output, and there was an exception thrown: ConcurrentModificationException. This exception was thrown when the second call to the next() method was made.

The idea is this: Once you start iterating through a collection in the Java Collections Framework, you should not modify the collection except with messages to that iterator. Otherwise, the integrity of that iterator may be compromised, so ConcurrentModificationException is thrown. Such iterators are fail-fast: the exception is thrown as soon as the iterator may be invalid. The alternative, waiting until the iterator is known to be invalid, may be far more difficult to detect.

The mechanism for making iterators fail-fast involves two fields: one in the collection, and one in the iterator. We have studied six Collection classes within the Java Collections Framework: ArrayList, LinkedList, Stack, PriorityQueue, TreeSet, and HashSet. Each of these classes has a modCount field¹ that is initialized to 0. Each time the collection is structurally modified, modCount—for "modification count"—is incremented by 1.

The iterator class embedded in the Collection class has an expectedModCount field, which is initialized to modCount in the iterator's constructor. Whenever the iterator structurally modifies the collection (for example, with a call to itr.remove()), both expectedModCount and modCount are incremented by 1. Also, whenever the iterator object itself is modified (for example, with a call to itr.next() or itr.remove()), there is a test:

if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

If modCount and expectedModCount are unequal, that means the collection has been structurally modified, but not by the iterator. Then for example, as in the program at the beginning of this section, a call to the next() method might advance to an element that is no longer in the collection. Instead of returning a possibly incorrect value, the next() method throws ConcurrentModificationException.

If, for some reason, you want to bypass this fail-fast protection, you can catch ConcurrentModificationException and do nothing in the catch block.

¹ For the ArrayList and LinkedList classes, modCount is inherited from AbstractList. TreeMap and HashMap explicitly declare the modCount field. TreeSet and HashSet utilize the modCount field in the backing map field (an instance of TreeMap and HashMap, respectively).