Using threads with collections, Part 1

Threads add a new degree of complexity to otherwise straightforward design issues

By Chuck Mcmanis, JavaWorld.com, 03/01/98

Some people simply do not register the statement, "The Java platform is multithreaded." Sure, they hear it, and they nod their heads. But they don't grasp that, unlike C or C++, in which threading was bolted on from the side through the OS, threads in Java are basic language constructs. This misunderstanding, or poor grasp, of the inherently threaded nature of Java, inevitably leads to two common flaws in programmers' Java code: Either they fail to declare a method as synchronized that should be (because the object is in an inconsistent state during the method's execution) or they declare a method as synchronized in order to protect it, which causes the rest of the system to operate inefficiently.

I came across this problem when I wanted a collection that multiple threads could use without needlessly blocking the execution of the other threads. None of the collection classes in the 1.1 version of the JDK are thread-safe. Specifically, none of the collection classes will allow you to enumerate with one thread while mutating with another.

Non-thread-safe collections

My basic problem was as follows: Assuming you have an ordered collection of objects, design a Java class such that a thread can enumerate all or part of the collection without worrying about the enumeration becoming invalid due to other threads that are changing the collection. As an example of the problem, consider Java's Vector class. This class is not thread-safe and causes many problems for new Java programmers when they combine it with a multithreaded program.

The Vector class provides a very useful facility for Java programmers: namely, a dynamically-sized array of objects. In practice, you might use this facility to store results where the final number of objects you will be dealing with isn't known until you are done with them all. I constructed the following example to demonstrate this concept.

01 import java.util.Vector;
02 import java.util.Enumeration;
03 public class Demo {
04     public static void main(String args[]) {
05         Vector digits = new Vector();
06         int     result = 0;
07 
08         if (args.length == 0) {
09             System.out.println("Usage is java demo 12345");
10             System.exit(1);
11         }
12 
13         for (int i = 0; i < args[0].length(); i++) {
14             char c = args[0].charAt(i);
15             if ((c >= '0') && (c <= '9'))
16                 digits.addElement(new Integer(c - '0'));
17             else
18                 break;
19         }
20         System.out.println("There are "+digits.size()+" digits.");
21         for (Enumeration e = digits.elements(); e.hasMoreElements();) {
22             result = result * 10 + ((Integer) e.nextElement()).intValue();
23         }
24         System.out.println(args[0]+" = "+result);
25         System.exit(0);
26     }
27 }

The simple class above uses a Vector object to collect digit characters from a string. The collection is then enumerated to compute the integer value of the string. There is nothing wrong with this class except that it is not thread-safe. If another thread happened to hold a reference to the digits vector, and that thread inserted a new character into the vector, the results of the loop in lines 21 through 23 above would be unpredictable. If the insertion occurred before the enumeration object had passed the insertion point, the thread computing result would process the new character. If the insertion happened after the enumeration had passed the insertion point, the loop would not process the character. The worst-case scenario is that the loop might throw a NoSuchElementException if the internal list was compromised.