Rule of thumb for choosing an implementation of a Java Collection?

Question

Anyone have a good rule of thumb for choosing between different implementations of Java Collection interfaces like List, Map, or Set?

For example, generally why or in what cases would I prefer to use a Vector or an ArrayList, a Hashtable or a HashMap?

Answer 1

I really like this cheat sheet from Sergiy Kovalchuk's blog entry, but unfortunately it is offline. However, the Wayback Machine has a historical copy:

More detailed was Alexander Zagniotov's flowchart, also offline therefor also a historical copy of the blog:

Excerpt from the blog on concerns raised in comments: "This cheat sheet doesn't include rarely used classes like WeakHashMap, LinkedList, etc. because they are designed for very specific or exotic tasks and shouldn't be chosen in 99% cases."

Answer 2

I'll assume you know the difference between a List, Set and Map from the above answers. Why you would choose between their implementing classes is another thing. For example:

List:

1. ArrayList is quick on retrieving, but slow on inserting. It's good for an implementation that reads a lot but doesn't insert/remove a lot. It keeps its data in one continuous block of memory, so every time it needs to expand, it copies the whole array.
2. LinkedList is slow on retrieving, but quick on inserting. It's good for an implementation that inserts/removes a lot but doesn't read a lot. It doesn't keep the entire array in one continuous block of memory.

Set:

1. HashSet doesn't guarantee the order of iteration, and therefore is fastest of the sets. It has high overhead and is slower than ArrayList, so you shouldn't use it except for a large amount of data when its hashing speed becomes a factor.
2. TreeSet keeps the data ordered, therefore is slower than HashSet.

Map: The performance and behavior of HashMap and TreeMap are parallel to the Set implementations.

Vector and Hashtable should not be used. They are synchronized implementations, before the release of the new Collection hierarchy, thus slow. If synchronization is needed, use Collections.synchronizedCollection().