Java Practices->Choosing the right Collection

Choosing the right Collection

Here's a guide for selecting the proper implementation of a

Set,
List

, or Map. It was compiled for Java 1.4. Many additions have been made to the Collections Framework since then (notably the Queue and Deque interfaces, and various items in java.util.concurrent). These later additions have been omitted here, since this briefer summary should suffice for most cases.

The best general purpose or 'primary' implementations are likely ArrayList, LinkedHashMap, and LinkedHashSet. Their overall performance is better, and you should use them unless you need a special feature provided by another implementation. That special feature is usually ordering or sorting.

For convenience, "ordering" will here refer to the order of items returned by an Iterator, and "sorting" will here refer to sorting items according to Comparable or Comparator.

Interface	HasDuplicates?	Implementations					Historical
`Set`	no	`HashSet`	...	`LinkedHashSet`	...	`TreeSet`	...
`List`	yes	...	`ArrayList`	...	`LinkedList`	...	`Vector, Stack`
`Map`	no duplicate keys	`HashMap`	...	`LinkedHashMap`	...	`TreeMap`	`Hashtable, Properties`

Principal features of non-primary implementations:

HashMap has slightly better performance than LinkedHashMap, but its iteration order is undefined
HashSet has slightly better performance than LinkedHashSet, but its iteration order is undefined
TreeSet is ordered and sorted, but slower
TreeMap is ordered and sorted, but slower
LinkedList has fast adding to the start of the list, and fast deletion from the interior via iteration

Iteration order for above implementations:

HashSet - undefined
HashMap - undefined
LinkedHashSet - insertion order
LinkedHashMap - insertion order of keys (by default), or 'access order'
ArrayList - insertion order
LinkedList - insertion order
TreeSet - ascending order, according to Comparable / Comparator
TreeMap - ascending order of keys, according to Comparable / Comparator

For LinkedHashSet and LinkedHashMap, the re-insertion of an item does not affect insertion order.

For LinkedHashMap, 'access order' is from the least recent access to the most recent access. In this context, only calls to get, put, and putAll constitute an access, and only calls to these methods affect access order.

While being used in a Map or Set, these items must not change state (hence, it's recommended that these items be immutable objects):

keys of a Map
items in a Set

Sorting requires either that:

the stored items implement Comparable
a Comparator for the stored objects be defined

To retain the order of a ResultSet as specified in an ORDER BY clause, insert the records into a List or a LinkedHashMap.