DATA EXPANSION IN NONCOLLECTION CLASSES
Many noncollection classes also store lots of data in an internal array. For example, the ByteAr-
rayOutputStream class must store all data written to the stream into an internal buffer; the
StringBuilder and StringBuffer classes must similarly store all their characters in an internal
Most of these classes use the same algorithm to resize the internal array: it is doubled each time it
needs to be resized. This means that, on average, the internal array will be 25% larger than the
data it currently contains.
The performance considerations here are similar: the amount of memory used is larger than in the
ArrayList example, and the number of times data must be copied is less, but the principle is the
same. Whenever you are given the option to size a object when it is constructed and it is feasible
to estimate how much data the object will eventually hold, use the constructor that takes a size
Collections and Memory Efficiency
We've just seen one example where the memory efficiency of collections can be suboptimal:
there is often some wasted memory in the backing store used to hold the elements in the col-
This can be particularly problematic for sparsely used collections: those with one or two ele-
ments in them. These sparsely used collections can waste a large amount of memory if they
are used extensively. One way to deal with that is to size the collection when it is created.
Another way is to consider whether a collection is really needed in that case at all.
When most developers are asked how to quickly sort any array, they will offer up quicksort
as the answer. Good performance engineers will want to know the size of the array: if the ar-
ray is small enough, then the fastest way to sort it will be to use insertion sort. (Algorithms
based on quicksort will usually use insertion sort for small arrays anyway; in the case of
Java, the implementation of the Arrays.sort() method assumes that any array with less
than 47 elements will be sorted faster with insertion sort than with quicksort.) Size matters.