ArrayList has three initialization methods
public ArrayList() public ArrayList(int initialCapacity) public ArrayList(Collection<? extends E> c)
The first parametric construction method
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}The note above says that the default capacity is 10. The DEFAULTCAPACITY_EMPTY_ELEMENTDATA above explains as follows:
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class accessActually, it's an empty array, so the parameterized constructor just points to an empty array.
Then look at the construction method with parameters.
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}Input of an initial capacity, greater than 0... = 0... <0...
It is necessary to mention that EMPTY_ELEMENTDATA is an empty array.
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};Look at the next construction method
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}This method directly converts a collection into an array and assigns it to elementData.
Implementation of add method
The usual add method is like this.
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}About modCount++ this operation I open a separate blog to introduce. Let's look at the function add(e,elementData,size)
size is the number of elements in the current array, excluding New ones.
/**
* This helper method split out from add(E) to keep method
* bytecode size under 35 (the -XX:MaxInlineSize default value),
* which helps when add(E) is called in a C1-compiled loop.
*/
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}When it is found that the number of elements is equal to the length of the array, it means that the expansion operation, namely the growth () function, will be performed. If it's not full, assign a value, and then the number of elements + 1.
Let's look at the growth () function:
private Object[] grow() {
return grow(size + 1);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}Look at the minCapacity=size+1 of the second function above. Execute the copy function to return the result to elementData. There are two parameters in the copy function. The first one is the old array, and the second one is the length of the expansion. The length of the new array is determined by the new Capacity (minCapacity). Let's look at this function
/**
* Returns a capacity at least as large as the given minimum capacity.
* Returns the current capacity increased by 50% if that suffices.
* Will not return a capacity greater than MAX_ARRAY_SIZE unless
* the given minimum capacity is greater than MAX_ARRAY_SIZE.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}Old Capacity is the length of the old array, and new Capacity is 1.5(bit operation) of the old array. The following if condition determines whether the length of the expanded array meets the length I want at this time. If the condition holds (new capacity <= minCapacity), that is to say, you can't do this expansion, or it's too small. Body,
Here DEFAULTCAPACITY_EMPTY_ELEMENTDATA, as mentioned above, is an empty array. If the elementData is an empty array, return the length of minCapacity directly as the length of the new array and throw an exception less than 0. Let's look at the bottom return statement again. If the expanded length meets the requirements at this time, what is this MAX_ARRAY_SIZE?
/**
* The maximum size of array to allocate (unless necessary).
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;After expansion, the length is smaller than MAX, and it meets the requirement to return to new Capacity. If the length after expansion is larger than the maximum, execute the hegeCapacity function.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}The logic here is simple, which is to determine whether the return is Integer.MAX_VALUE or MAX_ARRAY_SIZE by judging.