September 2, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

The Java Collections Framework: Implementations

  • December 7, 1999
  • By David Reilly
  • Send Email »
  • More Articles »

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.








Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel