This chapter requires us to familiar with the Collection interface and its sub interfaces -- what's the usage, what's the methods. We also need to compare a few implementations of the interfaces.
For experienced java programers, it is better to study this chapter with a later chapter:
Use java.util.concurrent collections and classes including CyclicBarrier and CopyOnWriteArrayList
ArrayList
TreeSet
TreeMap
ArrayDeque
Comparison of Implementations
+ means fast O(1)
* means normal O(log n)
- means slow O(n)
modify and retrieve performance measured at worst scenario (for example, if add/remove middle nodes is slow, but add/remove head/tail node is fast, it is marked as modify - )
| Class | Interfaces | Sorted? | use hashCode? | allow null? | performance | memory usage |
|---|---|---|---|---|---|---|
| ArrayList | List | No | No | Yes |
modify -, retrieve
|
normal |
| LinkedList | List, Queue | No | No | Yes |
modify +, retrieve -
All of the operations perform as could be expected for a doubly-linked list.
|
normal |
| HashSet | Set | No | Yes | Yes |
modify +, retrieve +
Backed by a HashMap instance. The add, remove, contains and size operations run in constant time. Iterating over this set requires time proportional to the sum of the number of elements plus the number of buckets.
|
low |
| TreeSet | Set | Yes | No | No |
modify *, retrieve *
The add, remove and contains operations take log(n) time cost.
|
high |
| ArrayDeque | Queue | No | No | No |
modify +, retrive +
Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time.
|
normal |
| HashMap | Map | No | Yes | Yes |
modify +, retrieve +
The get and put operations run in constant time. Iterating over this set requires time proportional to the sum of the number of elements plus the number of buckets. Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
|
low
The initial capacity and load factor effect HashMap performance. The initial capacity is the initial number of buckets. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the (number of entries) > (load factor) X (number of buckets), the hash table is rehashed and the number of buckets are roughly doubled. The default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost. Creating it with a sufficiently large capacity to avoid costly rehashing.
|
| TreeMap | Map | Yes | No | No |
modify *, retrieve *
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
|
high |
