Java Reference
In-Depth Information
private transient
transient Object [] elementData ;
As items are added and removed from the ArrayList , they are stored at the desired location
within the elementData array (possibly causing other items in the array to shift). Similarly, a
HashMap contains an array of an internal data type called HashMap$Entry , which maps each
key-value pair to a location in the array specified by the hashcode of the key.
Not all collections use an array to hold their elements; a LinkedList for example, holds each
data element in an internally defined Node class. But collection classes that do use an array to
hold their elements are subject to special sizing considerations. You can tell if a particular
class falls into this category by looking at its constructors: if it has a constructor that allows
the initial size of the collection to be specified, then it is internally using some array to store
the items.
For those collection classes, it is important to accurately specify the initial size. Take the
simple example of an ArrayList : the elementData array will (by default) start out with an
initial size of 10. When the 11th item is inserted into an ArrayList , the list must expand the
elementData array. This means allocating a new array, copying the original contents into
that array, and then adding in the new item. The data structure and algorithm used by, say, the
HashMap class is much more complicated, but the principle is the same: at some point, those
internal structures must be resized.
The ArrayList class chooses to resize the array by adding roughly half of the existing size,
so the size of the elementData array will first be 10, then 15, then 22, then 33, and so on.
Whatever algorithm is used to resize the array (see sidebar), this results in some wasted
memory (which in turn will affect the time the application spends performing GC). Addition-
ally, each time the array must be resized, an expensive array copy operation must occur to
transfer the contents from the old array to the new array.
To minimize those performance penalties, make sure to construct the collection with as ac-
curate an estimate of its ultimate size as possible.
Search WWH ::

Custom Search