Java Collection Performance

This is just a helpful reference when trying to decide which collections to use in Java. I use this for my personal reference but it may help others as well. The links go to the Sun Javadocs. The collections of each type are ordered based on performance (i.e. the highest performance (highest speed) ones are listed first and will be the fastest for most operations)

List - this is an ordered list of objects, insertion order is maintained and retrieval order is in the list order but items can also be random accessed, duplicate items are allowed, generally allow storage of null values (the ones below do), generally fast to iterate and find items by position but slow to do lookups

• ArrayList - Unsychronized, nulls allowed (fastest)
  
• Vector - Synchronized, only slightly slower in tests of sizes under 100000
• Stack - Synchronized, same speed as Vector, LIFO queue
• LinkedList - Unsynchronized, allows two way iteration and modification of items (like a stack or queue)
• CopyOnWriteArrayList - Synchronized, significantly slower in tests of large numbers of items or average list changes, only slightly slower when used with very small numbers (<100)>

Set - this a set of items with no duplicates (no two items can compare as equal), ordering is typically inconsistent over multiple set iterations depending on the implementation but you should assume the order is effectively random unless the set specifies ordered iteration, generally ok to iterate and fast to do lookups

• HashSet - Unsychronized (fastest), slower than HashMap which it is built on, allows nulls
  
• LinkedHashSet - Unsychronized, ordered by insertion, allows nulls
  
• TreeSet - Unsychronized, ordered by the natural ordering of the items or a comparator provided at construction, allows nulls but there are issues with removing them
  
• CopyOnWriteArraySet - Synchronized, significantly slower in tests of large numbers of items or average set changes, only slightly slower when used with very small numbers (<100)>

Map - Stores key/value pairs (maps keys to values) where the keys must be unique, order of iteration over keys, values, or pairs is highly dependent on the implementation of the map, allowed nulls also vary by implementation, generally very fast to lookup keys and slow to lookup values

• IdentityHashMap - Unsychronized (fastest), uses reference equality (==) instead of object equality (equals) to compare keys, actually violates the Map interface guarantee, all iterators are unordered, allows null keys and values
• HashMap - Unsychronized, this is the fastest general purpose map, all iterators are unordered, allows null keys and values
• ConcurrentHashMap - Synchronized, all iterators are unordered, does not allow null keys or values
• Hashtable - Synchronized, all iterators are unordered, does not allow null keys or values
• LinkedHashMap - Unsychronized, all iterators are ordered based on insertion order of the original key (does not change if a key is reinserted), allows null values but null keys are not allowed
  
• TreeMap - Unsychronized, iterators are ordered by the natural or comparator ordering of the keys, allows null keys and values but the comparator needs to understand them