1. An overview of the
ArrayList is a variable-length collection class based on a fixed-length array implementation. An ArrayList allows null and duplicate elements. When the number of elements added to an ArrayList exceeds the capacity of the underlying array, it creates a larger array through a scaling mechanism. In addition, ArrayList can guarantee random lookup operations under O(1) complexity because it is based on arrays. Otherwise, ArrayList is a non-thread-safe class. In a concurrent environment, multiple threads operating on ArrayList at the same time can cause unpredictable errors.
ArrayList is the most commonly used collection class. As a variable-length collection class, its core is the expansion mechanism. So just know how it expands and how the basic operations are done. The rest of this article focuses on the source code for ArrayList in JDK11 (18.9).
2. Source code analysis
2.1 parameter
ArrayList defaults to 10DEFAULT_CAPACITY
2. ArrayList does not create an array with DEFAULT_CAPACITY=10 when initialized. Instead, it expands to 10 elementData annotations when you add the first data
private static final long serialVersionUID = 8683452581122892189L;
/** * Default initialization capacity */
private static final int DEFAULT_CAPACITY = 10;
/** * Shared empty array instances for empty instances. * /
private static final Object[] EMPTY_ELEMENTDATA = {};
/** * 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. * Shared empty array instances for empty instances of default size. We separate this from EMPTY_ELEMENTDATA to see how much to inflate when adding the first element. * /
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. An array buffer that stores the elements of an ArrayList whose capacity is the length of the array buffer. When the first element is added, elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY */
transient Object[] elementData; // non-private to simplify nested class access
/** * The size of The ArrayList (The number of elements it contains). * Array size *@serial* /
private int size;
Copy the code2.2 Construction method
An ArrayList has three constructors: a no-argument constructor, an empty constructor with a specific initial capacity value, and a list containing the specified collection elements in the order in which they are returned by the collection iterator.
2.2.1 No-parameter construction method
Constructs an empty list with an initial capacity of ten note the comment Constructs an empty list with an initial capacity of ten that calls the no-argument constructor.
/** * Constructs an empty list with an initial capacity of ten. */
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code2.2.2 Construct empty methods with specific initial capacity values
1. Knowing how many elements will be inserted into the ArrayList. 2. Be sure to initialize the specified length.
/**
* 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); }}Copy the code2.2.3 Construct a list of the specified set elements in the order in which they are returned by the set iterator
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. Constructs a list of the specified collection elements, returning them in the order of the collection 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[]
// Defense c.toarray (incorrectly) does not return Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
// JDK bug (the behavior of the toArray() method of ArrayList is inconsistent with the specification)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeJDK-6260652 (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
In a nutshell, this is what the following code would do.
Object[] objects = new String[]{"string"};
objects[0] = 1;
/**
Exception in thread "main" java.lang.ArrayStoreException: java.lang.Integer
*/
Copy the codeThe reasons causing
public Object[] toArray() {
return a.clone();
}
Copy the codeThe behavior of the toArray() method of ArrayList implemented internally is inconsistent with the specification. According to the JLS specification, the clone method of String[] also returns String[], so the true type returned by toArray() is String[]. Therefore, the assignment of toArray()[0] may cause a type mismatch error
The toArray() method of ArrayList implemented internally from Arrays in JDK11. So calling copyOf() returns type Object[]
public Object[] toArray() {
return Arrays.copyOf(a, a.length, Object[].class);
}
Copy the code2.3 Common Methods
2.3.1 insert
For array (linear table) structures, insert operations fall into two categories. One is to insert at the end of the element sequence, and the other is to insert elsewhere in the element sequence. The ArrayList source code also shows both types of inserts, as follows:
/** * This helper method split out from add(E) to keep method * bytecode size under 35 (the -XX:MaxInlineSize default value), * This helper method helps when add(E) is called in a C1-compiled loop. This helper method is separated from add(E), in order to keep the method bytecode below 35, this will help add(E) to call C1 compiled loop. * /
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
/** private Object[] grow() { return grow(size + 1); } * * /
// Insert the new element at the end of the sequence
elementData[s] = e;
size = s + 1;
}
/** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). Inserts the specified element at the specified position in this list. Moves the element currently at that position (if any) and any subsequent elements to the right (adding an element to its index) *@param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc} * /
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// 2. Move index and all elements after it one bit back
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
// 3. Insert the new element at index
elementData[index] = element;
size = s + 1;
}
Copy the code2.3.1.1 Element sequence tail inserted
- Checks whether the array has enough space to insert
- Inserts the new element to the end of the sequence
The diagram below:
2.3.1.2 Element sequence specifies the position (assuming it is reasonable) to insert
- Checks if the array has enough space
- Move index and all elements after it one bit back
- Insert the new element at index
The diagram below:
The complexity is order N.
2.3.2 Capacity Expansion mechanism of ArrayList
For variable-length data structures, expansion is required when there is no free space available in the structure. In an ArrayList, when space runs out, it expands by 1.5 times the size of the original array. The relevant source code is as follows:
/** Expansion entry method */
/**
* Increases the capacity of this {@codeArrayList} instance, if * necessary, To ensure that it can hold at least the number of elements * specified by the minimum capacity argument.@codeArrayList} the capacity of the instance, if necessary, to ensure that it can hold at least the number of elements * specified by the minimum Capacity parameter@param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
/** Core method of expansion */
/** * 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. Returns the capacity capacity that is at least equal to the given minimum value. Return current capacity increased by 50%, if enough. No capacity greater than MAX_ARRAY_SIZE is returned 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); // Old capacity + increase the old capacity by 50% (moving 1 bit to the left equals dividing by 2)
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); }private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// If the minimum capacity exceeds MAX_ARRAY_SIZE, expand the array capacity to integer.max_value
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Copy the code2.3.3 delete
Unlike insert, ArrayList has no no-parameter delete method. So it can only delete elements in a specified position or delete a specified element, so it cannot avoid moving elements (except from the end of the element sequence). The relevant codes are as follows:
/** Removes the element */ at the specified position
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc} * /
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
// Returns the value of the deleted element
@SuppressWarnings("unchecked")
E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
/** Removes the first occurrence of the specified element (if present) from the list. If the list contains no elements, it does not change. More precisely, remove the element with the lowest index */
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* {@code Objects.equals(o, get(i))}
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
// Walk through the array to find the location of the element to be deleted
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
/** * Private remove method that skips bounds checking and does not * return the value removed. */
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
// Move the index + 1 and subsequent elements forward one bit to overwrite the deleted value
System.arraycopy(es, i + 1, es, i, newSize - i);
// Empty the last element and decrease size by 1
es[size = newSize] = null;
}
Copy the codeThe above delete method is not complicated, here is the first delete method as an example, delete an element steps are as follows:
- Gets the value of the element at the specified position index
- Move the index + 1 and subsequent elements forward one bit
- Empty the last element and decrease size by 1
- Returns the deleted value. The deletion is complete
The diagram below:
/** Reduces the array size to the number of elements */
/**
* Trims the capacity of this {@code ArrayList} instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an {@code ArrayList} instance.
*/
public void trimToSize(a) {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the code
trimToSize()
2.3.4 traversal
ArrayList implements the RandomAccess interface (which is a signature interface), showing that it is capable of fast RandomAccess. The underlying ArrayList implementation is based on arrays, so it can perform random access in constant order time, which is very efficient. For traversal of an ArrayList, we generally like to use a foreach loop, but this is not recommended. ArrayList has the capability of random access. In some scenarios requiring high efficiency, the following method is recommended:
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
Copy the codeThe website specifically states that using a for loop is better than using an iterator for a List that implements this interface
3. Other details
3.1 Quick Failure Mechanism
In the Java Collections framework, many classes implement a fast failure mechanism. The mechanism is triggered, throws concurrent modification abnormal ConcurrentModificationException, this exception everyone more or less in the usual development should be met. The quick failure mechanism is explained in the ArrayList comment, which is quoted here:
The iterators returned by this class’s iterator() and listIterator(int) methods are fail-fast if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own ListIterator remove() or ListIterator add(Object) methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Methods in an ArrayList iterator fail fast. In the case of concurrent changes, iterators fail fast to avoid uncertain behavior at indefinite times in the future.
That’s why the Java Collections framework introduced the fast failure mechanism, and it’s not hard to understand why I won’t go into more detail here.
3.2 About Traversal Deletion
Traversal deletion is an incorrect operation, and even if the code does not fail sometimes, the execution logic will fail. About this problem, Alibaba Java development manual has also been mentioned. Here’s a quote:
Do not remove/add elements in a foreach loop. The remove element must be Iterator. If the operation is performed concurrently, the Iterator must be locked.
The relevant code (with minor modifications) is as follows:
List<String> a = new ArrayList<String>();
a.add("1");
a.add("2");
for (String temp : a) {
System.out.println(temp);
if("1".equals(temp)){ a.remove(temp); }}}Copy the codeBelieve that some friends should have seen this, and also perform the above procedures. The above program will not execute although there is no exception, but there is a problem with the code execution logic, but this problem is hidden deeper. If we print out the temp variable, we’ll see that only the numbers 1,2 are printed. At first glance, the results of this implementation are really surprising, unknown reasons. If we dig into the code above, it’s hard to figure out why, so we need to think a little differently. We all know that Foreach in Java is a syntactic sugar that is converted to iterator traversal when compiled into bytecode. So we can convert the above code to equivalent to the following:
List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){ a.remove(temp); }}Copy the codeAt this point, we can analyze the iterator source code of ArrayList to find out why.
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext(a) {
returncursor ! = size; }@SuppressWarnings("unchecked")
public E next(a) {
// Concurrent change detection, detection does not pass, throw an exception
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification(a) {
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
// omit irrelevant code
}
Copy the codeStep by step, the first time we enter the while loop, everything is fine and element 1 is deleted. But once element 1 is deleted, the while loop cannot be entered again, where it.hasnext () is false. The reason is that after deleting element 1, the element counter size = 1 and the cursor in the iterator is equal to 1, causing it.hasNext() to return false. Ultimately, the reason the above code snippet didn’t throw an exception is that the loop ended prematurely, leaving the Next method without a chance to throw. If you don’t believe me, you can modify the code slightly to find the problem:
List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
a.add("3");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){ a.remove(temp); }}Copy the codeThis is the analysis of traversal deletion, which we should avoid in our daily development. The correct approach is to use the delete method provided by the iterator rather than delete directly.