September 12, 2007 by Craig
Java has three major types of collections:
- Lists: a collection of values with a precise (ie: user-defined) order. Duplicate values are allowed (which makes the List a Bag). You can access each element by an numeric index.
- Sets: a collection of values without a user-defined order. Duplicates are not allowed.
- Map: a collection of key-value pairs (ie: a mapping of keys to values).
These are then broken down into implementation-specific subtypes, each of which has applicable uses depending on the situation:
- Hash: Useful when very quick (O(1)) retrieval access is desired, iteration over the entire collection is rare, and sort order is unimportant. Ex: HashMap, HashSet. Hash doesn’t conceptually agree with the user-ordering or duplicates of a List so there is no HashList (HashSet is usually sufficient)
- Tree: Useful when quick (O(log n)) element access is desired, iteration over the entire collection is somewhat common, and sort order is important. Ex: TreeMap, TreeSet. Tree doesn’t conceptually agree with the user-ordering or duplicates of a List so there is no TreeList (TreeSet is usually sufficient)
- Array: Useful when you desire a List/Bag collection, especially if the approximate number of elements is known beforehand. Provides very quick (O(1)) retrieval if you know the element’s index (which can be very common in some circumstances). Ex: ArrayList. You could, in theory, make an ArraySet and ArrayMap, but they’d end up performing worse than HashSet/HashMap and wouldn’t provide much additional functionality, so they’re not implemented in the standard Java packages.
- Linked: Useful when the number of elements is not known beforehand (although ArrayList will still perform better in many cases). Ex: LinkedList. There’s also a LinkedHashSet which combines the features of a HashSet and a theoretical LinkedSet (which would be a very poor performer). Unfortunately there’s no LinkedHashMap in standard Java. LinkedList works well when you need a Queue or a Stack.
.NET has a similar yet deficient family of collections:
- IList: Pretty much identical to Java’s List. Can be used as a Bag as well.
- IDictionary: Pretty much identical to Java’s Map.
- There is no “Set” equivalent in .NET. If you want a collection that guarantees no duplicates, you have to enforce that yourself (although there does exist a 3rd-party library that includes ISet; this library is included in NHibernate).
The implementations are even more sporadic:
- List: Equivalent to Java’s ArrayList.
- Dictionary: A hash table, which makes it equivalent to Java’s HashMap.
- LinkedList: Equivalent to Java’s LinkedList.
- SortedDictionary: Equivalent to Java’s TreeMap.
- SortedList: Despite the name, this is not a Sorted (Tree) implementation of IList. In fact it implements IDictionary and duplicates all of the functionality of SortedDictionary. It even has the same retrieval profile (O(log n)) of SortedDictionary; the only difference is in it’s memory usage (lower) and insertion/removal performance (slower). If you don’t want a key-value pair mapping, then you are forced to choose between the linear-focused List and LinkedList, both of which are O(n) for insertion and searching.
- Queue: Is not an IList or IDictionary (just an ICollection), and doesn’t say much about its implementation / performance profile, although it’s probably a linked list under the covers.
- Stack: Same as Queue, except it’s LIFO instead of FIFO, and has a different interface (which is also not shared with IList).
In Java, I regularly used 5 different collection implementations depending on the circumstances; in .NET I only have 3 that are normally useful, and the gaps are not easily filled.