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:

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:

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:

• whether you need to maintain the keys in sorted order, in some fixed order or whether no particular order is required;
• whether you require efficient concurrent access (i.e. where multiple threads can access the map efficiently and can perform atomic updates on the map).

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

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:

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 need¹.

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).