http://www.developer.com/java/ent/article.php/618081/The-Java-Collections-Framework-Implementations.htm

Back to article

The Java Collections Framework: Implementations


December 7, 1999

In part one of this article, we covered the basic interfaces provided by the collections framework. Next, we'll examine the data structure implementations that the new collections framework provides, and some examples of their usage.

Implementations of the 
Collection
 and 
Map
 Interfaces 

There are many implementations of the 

Collection
and 
Map
 interfaces. Some you'll find familiar ( 
Vector
 and 
HashTable
), and others are new. The following table introduces the new classes, and shows which 
Interface
 each implements.

Implementations
Set SortedSet List Map SortedMap
HashSet TreeSet Vector / Stack Hashtable TreeMap
ArrayList HashMap
LinkedList WeakHashMap

Figure 1. Non-abstract classes that implement 

Collection
and 
Map
 interfaces.

Selecting a Collection or Map implementation

When using the new classes, it is important to remember that some implementations impose additional restrictions on what elements, keys and values may be safely stored and retrieved. For example, both 

SortedSet
and 
SortedMap
 require that elements implement the new 
Comparable
 interface. Some additional restrictions may include that elements are not 
null
, while other implementations may permit 
null
 elements.

The 

Collection
and 
Map
 interfaces (discussed earlier in Part One) provide a consistent mechanism for accessing these new data structures, so in many situations the choice of data structure is transparent. However, for performance reasons, one data structure may favor a particular set of circumstances over another. Additionally, using a 
List
 over a 
Set
 will allow duplicate storage of objects.
ArrayList

The 

ArrayList
class is a resizable array, and very similar in nature to a 
Vector
. The chief difference is that, like many other 
Collection
 implementations, it is not synchronized. This should give a mild performance increase in single-threaded applications.
LinkedList

LinkedList
offers methods for access ( 
addFirst/addList
), retrieval ( 
getFirst/getLast
) and deletion ( 
removeFirst/removeLast
) of the first and last elements of the list, in addition to the standard 
List
 methods. This functionality is extremely important, as it makes the 
LinkedList
 more versatile than an 
ArrayList
. For example, a stack which is a last-in-first-out (LIFO) queue needs the ability to insert data into the beginning of a list, and then remove it.
HashSet

The 

HashSet
class offers a 
Set
 implementation, which uses a hash table implementation to offer good addition, removal and access performance. For the benefit of those who have never written a hash table implementation before, an array index value (hash code) is calculated. This is determined by using a hashing function which attempts to calculate a unique value for each object. We can remove and access 
HashSet
 elements, as well as add new ones, in what is termed constant computing time (the time to calculate the hash code and add/remove/select the element is almost uniform, even as the number of elements increase). 
TreeSet

Unlike 

HashSet
, the 
TreeSet
 class sorts its elements in ascending order. This gives a slightly slower speed a hash table implementation (log(n) time rather than constant computing time), but in many situations this is worth it, for the guarantee that the set is sorted. 
HashMap

HashMap
differs very little from the Hashtable class. The chief difference is that its methods are unsynchronized, and it also accepts 
null
 values.

WeakHashMap

This class is extremely interesting, in that it uses weak keys. When there is no object reference to a particular key, it may be reclaimed by the automatic garbage collector. In other 

Map
implementations, the key will be protected from automatic reclamation,  as the 
Map
 maintains a reference to it. There is no such protection with a 
WeakHashMap
, so keys may be deleted (and hence the mapping to a value) without warning. This functionality is actually quite useful, as it saves having to manually remove unwanted entries.
TreeMap

TreeMap
implements the SortedMap interface, which sorts mapping by key. For this reason, data inserted into a 
HashMap
 must implement the 
Comparable
 interface. If sorting is important,  then use 
TreeMap
, which offers log(n) time for 
containsKey, get, put
 and 
remove
. If not, one of the 
HashMap
 implementations may be more appropriate.

Retrieving data from a collection

Adding data to a collection, or checking if an element exists, is relatively straightforward, particularly for those already familiar with the 

Vector
class. A big change though, is the way in which data elements are accessed. Readers may be familiar with the 
java.util.Enumeration
 interface, which offers a way to iterate through a series of data elements. The collection framework introduces a replacement: the 
Iterator
.

The 

Iterator
makes it easier to traverse through the elements of a collection. It also has an extra feature not present in the older Enumeration interface - the ability to remove elements. This makes it easy to perform a search through a collection, and strip out unwanted entries. The following example demonstrates the 
Iterator
 in action. It adds every command line parameter to a 
Collection
, then uses an 
Iterator
 to strip out parameters not beginning with a hyphen ('-'). 
import java.util.*;

public class IteratorDemo 
{
    public static void main(String args[])
    {
        Collection c = new ArrayList();

        // Add every parameter to our array list
        for (int indx = 0; indx < args.length; indx++)
        {
            c.add(args[indx]);
        }

        // Examine only those parameters that start with -
        Iterator i = c.iterator();

        // PRE : Collection has all parameters
        while (i.hasNext())
        {
            String param = (String) i.next();

            // Use the remove method of iterator
            if (! param.startsWith("-") )
                i.remove();
        }
        // POST: Collection only has parameters that start with -

        // Demonstrate by dumping collection contents
        Iterator i2 = c.iterator();
        while (i2.hasNext())
        {
            System.out.println ("Param : " + i2.next());
        }
    }
}

Synchronizing access to a Collection or Map

The 

Collection
and 
Map
 interfaces don't offer synchronized methods. However, collections are just as relevant in multi-threaded applications as they are in single-threaded ones!  Fortunately, there is an easy solution. 

Included in the collections framework are some support classes. One feature you'll find particularly handy is the ability to produce a synchronized version of a collection or map, using the 

Collections
class (not to be confused with the 
Collection
 interface). This is best done when first constructing it, to prevent a thread accessing an unsynchronized version. Methods are provided to create either a 
Collection, List, Set, SortedSet, Map
 or 
SortedSet
. For example, to created a synchronized 
TreeSet
, you could do the following: -

SortedSet set = Collections.synchronizedSortedSet(new TreeSet());

This produces a synchronization wrapper, which is a class that provides synchronized access to a collection. Failure to use synchronization wrappers can lead to concurrency problems, and a 

ConcurrentModificationException
being thrown.

Converting from a Collection to an array - and back again

The 

Collection
interface defines the 
 toArray()
 method, which returns an array of objects. If you want to convert back to a 
Collection
 implementation, you could manually traverse each element of the array and add it using the 
add(Object)
 method. 

// Convert from a collection to an array
Object[] array = c.toArray();

// Convert back to a collection
Collection c2 = new HashSet();
for (int i = 0; i < array.length; i++) { c2.add(array[i]; }

That's a little bit of work though. If you're happy enough to use a 

List
, rather than a 
Set
, the 
Arrays
 support class has a method which converts from an array to a list.

// Convert from a collection to an array
Object[] array = c.toArray();

// Convert back to a collection
Collection c2 = ArrayList.asList(array);

Either way, converting between collection and array (or vice versa) is relatively straightforward.

Putting the Collections framework to use

The collections framework makes it easy to create data structures with specialized behavior. When writing new data-types, you can implement or extend a 

Collection/Map
(for an is-a relationship), or use an existing collection as a member variable (for a has-a relationship).

For example, if you wanted to create a stack, you could use the 

LinkedList
class. Though a stack implementation already exists in the form of 
java.util.Stack
, the exercise of creating a stack is a useful learning aid. As you can see, the code is extremely compact and clear. 
LinkedList
 makes a good base for any type of queue, stack or double-ended queue. For example, a custom queue might accept only a certain type of object (such as 
Runnable
 instances for a thread pool). 
import java.util.*;

public final class SimpleStack 
{
    private LinkedList list = new LinkedList();

    public void push( Object o )
    {
        list.addFirst( o );
    }

    public Object pop()
    {
        Object o = list.getFirst();
        list.removeFirst();
        return o;
    }

    public boolean isEmpty()
    {
        return ( list.size() >0 ? false : true );
    }

    public int size() { return list.size(); }
}

Let's look a little further at some of the implementations. As mentioned above, some 

Collection
implementations guarantee the sorting of data elements, whereas others do not. Some guarantee only one occurrence of an element, others do not. Now's the time to see the differences in action! Take a look at the following listing, which adds random numbers to a collection. A 
Set
 will not allow duplicates, whereas a 
List
 will. A 
Set
 doesn't guarantee order, but a 
SortedSet
 does. By commenting and un-commenting the lines highlighted in bold, you can see the difference between them.

import java.util.*;

public class CollectionDemo 
{
    public static void main(String args[])
    {
        Collection c;
        Random r = new Random();

        c = new ArrayList();
        //c = new HashSet();
        //c = new TreeSet();

        for (int count = 1; count < 100; count++)
        {
            // Add a number between one and ten
            int num = r.nextInt();
            num = num < 0 ? -num : num;

            c.add ( new Integer (num % 10 +1) );
        }

        Iterator i = c.iterator();

        while (i.hasNext())
        {
            System.out.println (i.next());
        }
    }
}

Here's an extra tip for when you want to sort a 

List
. Since there isn't a 
SortedList
 interface, and a 
SortedSet
 isn't always appropriate, you must rely on the 
Collections
 class. The static 
Collections.sort(List)
 method will automatically sort a 
List
 for you. Try the following changes to the example, to demonstrate sorting with a 
List
 (which will then contain duplicate but ordered elements).

import java.util.*;

public class CollectionDemo 
{
    public static void main(String args[])
    {
        Collection c;
        Random r = new Random();

        c = new ArrayList();

        for (int count = 1; count < 100; count++)
        {
            // Add a number between one and ten
            int num = r.nextInt();
            num = num < 0 ? -num : num;

            c.add ( new Integer (num % 10 +1) );
        }

 Collections.sort ( (List) c );
        Iterator i = c.iterator();

        while (i.hasNext())
        {
            System.out.println (i.next());
        }
    }
}

Summary

The collections framework, and the new data structure implementations it provides, is a powerful tool for aggregation of objects. Almost any type of application or applet can benefit from using collections, and they offer much greater versatility than the simple 

Vector, Stack
and 
Hashtable
 classes. However, this functionality is part of the Java 2 platform - so it is currently incompatible with many browsers and JVMs. This will change in time though, and it's wise to become familiar with the collections framework now. Finding a use for collections won't be difficult, and will save many hours of coding custom data-structures.

About the author

David Reilly is a software engineer and freelance technical writer living in Australia. A Sun Certified Java 1.1 Programmer, his research interests include the Java programming language, and networking & distributed systems. He can be reached via email at java@davidreilly.com, or at his personal website.


Sitemap | Contact Us