[an error occurred while processing this directive]

How to choose which Java collection class to use? (ctd)

On the previous page, we outlined the different types of collection. Usually, the general type of collection is more or less clear. In particular, it's usually clear whether you need to use a map or not (are you storing associations between values/objects, or just a simple "bunch of things"?). But having chosen the general type, which Java collection class to then use can depend on a number of factors.

Remember that when picking a class from one of the sections below, the rule of thumb is:

If you can help it, don't pick a class that has features you don't need: you're likely to be paying for that feature in decreased efficiency.

In particular, some collections automatically sort the data as you add items to the collection. If you do need the data to be sorted, it's usually more efficient to pick an explicitly sorted collection than to use a normal one and then sort the data yourself. On the other hand, if you don't need sorting at all, then it is usually more efficient not to use a sorted collection. Nothing's free in life...

Which Java List to use?

A list is the simplest of structures. It keeps its elements in the same order in which they are inserted and allows duplicates. There are essentially three underlying list classes:

ClassFeatures/implementationWhen to use
ArrayList
  • Allows elements to be efficiently read by index.
  • Adding/removing the last element is efficient.
  • Not synchronized in any way.
In most cases.
LinkedList
  • First and last elements can be accessed efficiently;
  • Other elements cannot be efficiently accessed by index;
  • Not synchronized in any way.
Effectively, functions as a non-synchronized queue. In practice, rarely used: when you need a queue, you often need it to be concurrent or to provide other functionality; other implementations are often more useful.
CopyOnWriteArrayList
  • Allows safe concurrent access;
  • Reads are efficient and non-blocking;
  • Modifications are not efficient (since a brand new copy of the list is taken each time).
Where you need concurrent access and where frequency of reads far outweights frequency of modifications.

If you need concurrent access to a list and CopyOnWriteArrayList is not appropriate (either because the list is large or because reads don't outnumber writes), then the best you can really do is place a synchronized wrapper around an ordinary ArrayList:

List l = Collections.synchronizedList(new ArrayList());

Note that this gives you thread-safe access, but it's not truly concurrent in the sense that each access to the list will lock the entire list during the access.

Remember if you do this that you must always synchronize on the list while iterating over it (and in some cases this could be bad for concurrency). In practice, you should think carefully whether this type of list makes much sense. If a list is being continually altered by different threads, for example, what value do the individual index numbers really have?

Which Java Map to use?

The JDK provides various Map implementations depending on:

Depending on these requirements, the various Map implementations are as follows:

Ordering of keysNon-concurrentConcurrent
No particular orderHashMapConcurrentHashMap
SortedTreeMapConcurrentSkipListMap
FixedLinkedHashMap

Which Java Set to use?

Conceptually, a set serves to record whether or not an object belongs to a particular group. But a set is usually implemented as a degenerate type of map, in which each item added to the set is mapped to some special object meaning "present in the set". Therefore, especially in the non-current case, the choices in deciding which set implementation to use are largely similar to in the previous section: do you need a predictable iteration order and/or concurrent access? The available Set implementations are then as follows:

Ordering of keysNon-concurrentConcurrent
No particular orderHashSet
SortedTreeSetConcurrentSkipListSet
FixedLinkedHashSetCopyOnWriteArraySet

Perhaps surprisingly, Java doesn't provide a set implementation based on ConcurrentHashMap, though you could make such a subclass trivially yourself. Another option that requires no code is to use a ConcurrentSkipListSet, although you will be paying (in efficiency) for sorting that you don't really need1.

As with CopyOnWriteArrayList (on which it is actually based), the CopyOnWriteArraySet class is suited to cases where the set is relatively small and reads far outweight writes. Any modification of the set is expensive (since a brand new copy is created each time), but reads are non-blocking.

Which Java Queue to use?

See the separate section on Java queues for a list of the various queue classes and their functionality.

As mentioned above, if you need a queue that provides no extra features such as thread-safe access or sorting, then a simple LinkedList can be used.


1. The time taken to access a skip list structure increases by some constant amount each time the number of elements doubles; the time to access a hash table, as in HashMap and HashSet, is effectively constant no matter how many elements are in the set).