Tuesday, January 06, 2009

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

16 comments:

Anonymous said...

Great and useful post, megacheers!

-steve

A W M said...

jav-collections.blogspot.com

A W M said...

jav-collections.blogspot.com

A W M said...

jav-collections.blogspot.com

Anonymous said...

javolution contains some very fast implementation of collections ( javolution.org )

Taylor said...

I'm sorry - this seems entirely out of context. What does "fast" mean? For inserts? Removals? Bulk operations. Serial operations? Concurrent Operations?

Eyal Lupu said...

I must agree with Taylor – seems a little bit out of context – for example: ArrayList is fast as long as you know the size in advance (or as long as you don’t have many resizing) and as long as you don’t have many removals. On the other hand there are memory considerations – LinkedList has the pointers overhead but a large ArrayList might require a big chunk of contiguous memory to be allocated on a resize operation, also a large empty ArrayList is a big waste of memory.
Same for CopyOnWriteArrayList – the performance issue in here is also depending on the usage: modification of the list might cost (it is synchronized and allocates a new list) however it is very efficient for concurrent iteration and you are safe from the concurrent modification exception.

Dimitris Andreou said...
This comment has been removed by the author.
Dimitris Andreou said...

Quite superficial summary and presentation.

If one is to choose collection implementations without really understanding data structures, then the next best thing is a thorough decision tree, which at its leaves have all collections. That would be very helpful for such programmers. Yes, it would be tedious to construct this (correctly), but it would really offer something useful that could be used as a reference.

Paras Jain said...

Great post for ready reference. Every now and then developer faces the question - which collection to use??? This might help him to decide

Jari Mäntylä said...

Nicely put together. I use Collections on a daily basis; yet I learned something here.

Dimitris made a good proposition. The "decision tree" would be a great follow-up.

philho said...

I agree with Taylor, and showing what is the test code or at least methodology could have been better.
FYI, you should check for typos (Unsychronized...).
Yes, it is a useful introduction for newcomers to Java (I searched such information at the time) in compact form.
I wonder why you link to Java 1.5 in 2009... :-) You have probably your reasons, but perhaps you should mention why.

Andrew Binstock said...

If you actually want timings to verify these assertions, see Kent Beck's book, "Implementation Patterns" in which he does numerous timins and graphts the results.

Purohit D said...

Sun Java is one of the most flexible platform for application development Sun Java development gives the way to develop complex applicaton development.

falp said...

Really good quick reference

Andrew said...

Cool article about sets performance http://blog.griddynamics.com/2011/03/ultimate-sets-and-maps-for-java-part-i.html