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.
