Java Collections QuickRef

As of version 6.0, Java contains a large number of Collection classes. In this post, I have attempted to categorize a useful subset of these classes on the basis of general usage scenarios:

If you want to manage a Sequence of elements, and the sequence is:

• Unordered, use a Set
• If you do not need thread safety - use a HashSet
• If you need thread safety:
• Use a CopyOnWriteArraySet (under special conditions: small Set sizes and a very high read/write ratio)
• Or wrap a HashSet with a lock (Collections.synchronizedSet() can be used for this)
• Ordered:
• If the order is External, use a List
• If you do not need thread safety - use an ArrayList or LinkedList
• If you need thread safety:
• Use a CopyOnWriteArrayList (under special conditions: small List sizes and a very high read/write ratio)
• Or wrap a List with a lock (Collections.synchronizedList() can be used for this)
• If the order is Internal, use a SortedSet (an internal order is based on a 'natural' order relation defined on the elements of a container)
• If you do not need thread safety - use a TreeSet
• If you need thread safety - use a ConcurrentSkipListSet
  

If you want to manage a Mapping of keys to values, and the mapping needs to be:

• Unordered, use a Map
• If you do not need thread safety - use a HashMap
• If you need thread safety - use a ConcurrentHashMap
• Ordered (because you need to iterate through the container in a specified order)
• If the order is External, use a Map
• If you do not need thread safety - use a LinkedHashMap
• If you need thread safety - wrap a LinkedHashMap with a lock (Collections.synchronizedMap() can be used for this)
• If the order is Internal, use a SortedMap (an internal order is based on a 'natural' order relation defined on the elements of a container)
• If you do not need thread safety - use a TreeMap
• If you need thread safety - use a ConcurrentSkipListMap
  

If you want to Hold elements for future processing:

• If you do not need thread safety, use a Queue or Deque
• If you want:
• FIFO/LIFO ordering - use an ArrayDeque
• Priority based ordering - use a PriorityQueue
• If you need thread safety in (a producer-consumer situation), use a BlockingQueue or BlockingDeque
• If you want:
  
• FIFO/LIFO ordering - use a LinkedBlockingQueue or LinkedBlockingDeque
• Priority based ordering - use a PriorityBlockingQueue
  

The following table presents the Big-Oh time-complexity of common Collection operations for some of the core implementation classes:

	add(e)	add(i,e)	contains(e)	get(i)/ get(key)	iterator .next()	remove(0)	iterator .remove()
ArrayList	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)
LinkedList	O(1)	O(n)	O(n)	O(n)	O(1)	O(1)	O(1)
Hash table based	O(1)		O(1)	O(1)	O(h/n)		O(1)
Tree based	O(log n)		O(log n)	O(log n)	O(log n)		O(log n)
Skip list based	O(log n)		O(log n)	O(log n)	O(1)		O(log n)

For detailed information on Java Collections - Java Generics and Collections, by Naftalin and Wadler - is a great resource.

Efficient Concurrency

There are many ways to write thread-safe code for situations where concurrent readers and writers modify a shared data-structure:

• Using locks: but this is very inefficient under high read-write load, especially because multiple readers interfere with each other.
• Using read-write locks: this works better, because readers can run concurrently while no writes are taking place.
• Using non-blocking algorithms based on the Compare-and-Swap (CAS) primitive: this works very well at low to moderate load levels, but makes the application code more complicated.
• Using striping: where different sections of a large structure are protected with different locks (java.util.concurrent.ConcurrentHashMap uses this technique)
• Using copy-on-write structures: where a new copy of a structure is made on every write. Reads do not interfere with each other. This works well if the number of reads are much, much higher than the number of writes.
• Using immutable, functional structures: this is arguably the best way to manage concurrency. Reads do not interfere with each other. Writes need to acquire a lock for a very short time while replacing the root of the structure.

On to some real code. Here's an immutable/functional List that I recently implemented:
http://jiva.googlecode.com/svn/trunk/jiva/src/net/xofar/util/collection/immutable/List.java


The basic ideas behind the implementation of the above class are:

• The List class is abstract.
• List has two subclasses: Cons and Nil.
• Nil stands for an empty list.
• A Cons has two cells. One holds a value; the other points to the rest of the List. So a Cons essentially implements a singly-linked list.
  
• The last entry in a list is a Nil. At this point in the list, the rest of the list is empty.
• As a user of the List class, you never see Cons and Nil. You create a List using a factory method, and then use List operations to work on the list.
• The core List operations are:
  

public List<T> prepend(T elem)
public T head();
public List<T> tail();
public boolean isEmpty();
public List<T> remove(T elem);

Some interesting things to note about these operations are:

• The only way you can add something to a list is to prepend() to it. This returns a new list with the additional element. Threads that already hold a reference to the list continue to see the list as it was before the prepend.
• head() and tail() give you a clean way to iterate through the list.
• isEmpty() allows you to check for the end of the list.
• As a concession to the need for modification, List supplies a remove(T elem) method. This gives you back a new list that does not contain the supplied element. The implementation of this method uses an optimized form of copy-on-write.

In a future post, I will talk about a good use for immutable/functional lists in a highly concurrent situation. These kinds of lists also lend themselves very well to algorithms that build their results in a bottom-up fashion (this will be the subject of yet another post).