This article around JDK1.8 version to analyze the source of ArrayList, read the source code in order according to the constructor -> common API(add, delete, change, search) to parse the source code, understand the characteristics of ArrayList, use scenarios, etc..
The body of the
ArrayList is a dynamic array whose underlying data structure is still an array. It implements the List
, RandomAccess, Cloneable, java.io.Serializable interfaces. RandomAccess represents its ability to access randomly fast, and ArrayList can access elements by subscript with O(1) time complexity.
Since its underlying data structure is an array, it is conceivable that it has a capacity (the length of the array), and when the number of elements in the collection exceeds this capacity, the operation will be expanded. ArrayList(int initialCapacity) {} public ArrayList(int initialCapacity) {} public ArrayList(int initialCapacity) {} To reduce the number of capacity expansion, improve efficiency
Alternatively, you can manually call public void ensureCapacity(int minCapacity) {} to expand capacity. (ArrayList) List).ensurecapacity (30); (ArrayList).ensurecapacity (30);
A constructor
// An empty array in the default constructor
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// The underlying implementation of storing collection elements: an array that actually holds elements
transient Object[] elementData; // non-private to simplify nested class access
// The current number of elements
private int size;
// Default constructor
public ArrayList() {
// The default constructor simply assigns an empty array to elementData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/ / an empty array
private static final Object[] EMPTY_ELEMENTDATA = {};
// Constructor with initial capacity
public ArrayList(int initialCapacity) {
// if the initialCapacity is greater than 0, create an Object array of length initialCapacity.
// Notice that there is no change in size(compared to the third constructor)
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// If the capacity is 0, assign EMPTY_ELEMENTDATA directly to elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {If the capacity is less than 0, an exception is thrown
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}// Use other collection classes to build ArrayList constructors
public ArrayList(Collection<? extends E> c) {
// Use collection.toarray () directly to get an array of objects and assign it to elementData
elementData = c.toArray();
// Since size represents the number of elements in the collection, we assign size when constructing an ArrayList from another collection
if((size = elementData.length) ! =0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elementData.getClass() ! =Object[].class)Array.copyof copies elements from collection C into elementData array when c. array failed to return Object[]
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// If set C has 0 elements, the empty array EMPTY_ELEMENTDATA is assigned to elementData
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeTo summarize, once the constructor is done, it builds the array elementData and the quantity size. Note the collection.toarray () method, which is frequently used to retrieve all elements of a Collection in the source code of Collection subclasses.
CopyOf (elementData, size, Object[].class), which is to construct a generic array according to the type of class to decide whether it is new or reflected, and at the same time use native functions to batch assign elements to the new array. As follows:
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
// Construct a generic array based on the class type, new or reflection
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// Use native functions to batch assign elements to the new array.
System.arraycopy(original, 0, copy, 0.Math.min(original.length, newLength));
return copy;
}
Copy the codeNote that System. Arraycopy is also a very high frequency function.
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
Copy the codeCommonly used API
1,
Before each add, the system determines whether the capacity needs to be expanded.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;// Append an element to the end of the array and change size
return true;
}
private static final int DEFAULT_CAPACITY = 10;// Expand the capacity by 10 by default
private void ensureCapacityInternal(int minCapacity) {
// Use == to determine if the array is initialized with the default constructor
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;// modCount will be modified if expansion is determined
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// If capacity needs to be expanded, the capacity needs to be expanded by half by default
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);// By default, the capacity is increased by half
if (newCapacity - minCapacity < 0)// If that is not enough, use the smallest number you can hold. (Capacity after add)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);// Copy, expand, build a new array,
}
Copy the codepublic void add(int index, E element) {
rangeCheckForAdd(index);// Check if the exception is thrown out of bounds
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // Move the start of index back one bit
elementData[index] = element;
size++;
}
Copy the codepublic boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount // Confirm whether expansion is required
System.arraycopy(a, 0, elementData, size, numNew);// Copy the array to complete the copy
size += numNew;
returnnumNew ! =0;
}
Copy the codepublic boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);// Cross the line
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount // Confirm whether expansion is required
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);// Move (copy) array
System.arraycopy(a, 0, elementData, index, numNew);// Copy the array to complete the batch assignment
size += numNew;
returnnumNew ! =0;
}
Copy the codeSummary: Add, addAll. First determine whether it is out of bounds and whether it needs to be expanded. If you expand, copy the array. Then set the corresponding subscript element value.
It is worth noting:
- If the capacity needs to be expanded, the capacity will be expanded by half by default. If half of the capacity is not enough, use the target size as the capacity after expansion.
- ModCount is modified after capacity expansion is successful
2, delete
public E remove(int index) {
rangeCheck(index);// Determine if the boundary is crossed
modCount++;// Modify modeCount because the structure has changed
E oldValue = elementData(index);// Read the value to be deleted
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);// Overwrite array data with copy
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// Take the value from the array based on the index and force it
E elementData(int index) {
return (E) elementData[index];
}
// Remove the element from the position where it first appeared in the array. Returns true if there is, false if.
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);// Delete elements according to index
return true; }}else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
// There is no need to take out the element.
private void fastRemove(int index) {
modCount++;/ / modify modCount
int numMoved = size - index - 1;// Count the number of elements to move
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);// Copy the overwrite element to complete the deletion
elementData[--size] = null; // clear to let GC do its work
}
// Batch delete
public boolean removeAll(Collection
c) {
Objects.requireNonNull(c);/ / found empty
return batchRemove(c, false);
}
// Batch move
private boolean batchRemove(Collection
c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;//w represents the number of elements left in the array after batch deletion
boolean modified = false;
try {
// An efficient algorithm for saving the common elements of two sets
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) // If c does not contain the current index element,
elementData[w++] = elementData[r];/ / is retained
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if(r ! = size) {// An exception will cause r! =size, then all data after the exception will be copied and overwritten into the array.
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;// Change the number of w
}
if(w ! = size) {// Empty the element after the array
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;/ / modify modCount
size = w;/ / modify the size
modified = true; }}return modified;
}
Copy the codeFrom this we can also see that when there are more elements in the set used as the deleted element than in the deleted set, it is fine, only the elements that are jointly owned by them are deleted.
Summary:
- Delete operations definitely modify modCount and may involve copying arrays, which is relatively inefficient.
- Batch deletion, which involves efficient algorithms to save the common elements of two sets, can be noted.
3, change
ModCount is not modified, which is relatively efficient
public E set(int index, E element) {
rangeCheck(index);// Out of bounds check
E oldValue = elementData(index); // Fetch the element
elementData[index] = element;// Overwrite the element
return oldValue;// Return the element
}
Copy the code4,
ModCount is not modified, which is relatively efficient
public E get(int index) {
rangeCheck(index);// Out of bounds check
return elementData(index); // subscript data
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the code5. Clear up
Will modify modCount
public void clear() {
modCount++;/ / modify modCount
// clear to let GC do its work
for (int i = 0; i < size; i++) // Set all elements to null
elementData[i] = null;
size = 0; / / modify the size
}
Copy the code6, contain
// The normal for loop looks for a value, but it loops twice. Look for null the first time and look for the corresponding value the second time.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// A normal for loop looks for a value, but it loops twice. Look for null the first time and look for the corresponding value the second time.
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the code7. Empty isEmpty()
public boolean isEmpty() {
return size == 0;
}
Copy the codeIterator Iterator.
public Iterator<E> iterator() {
return new Itr();
}
/** * An optimized version of AbstractList.Itr */
private class Itr implements Iterator<E> {
int cursor; // Index of next element to return // Default is 0
int lastRet = -1; // index of last element returned; -1 if no such // last returned element (deleted flag bit)
int expectedModCount = modCount; // A flag to determine whether the collection has changed its structure
public boolean hasNext() {
returncursor ! = size; } @SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)// Determine if the boundary is crossed
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)// The List was modified by an asynchronous thread in our case
throw new ConcurrentModificationException();
cursor = i + 1;/ / the cursor + 1
return (E) elementData[lastRet = i];// Returns the element and sets the index of the last returned element
}
public void remove() {//remove the last next element
if (lastRet < 0)// Check whether next passes
throw new IllegalStateException();
checkForComodification();// Check whether it has been modified
try {
ArrayList.this.remove(lastRet);// Remove the element and modCount will be modified in the remove method, so the Iterator will be updated later
cursor = lastRet; // The cursor to delete
lastRet = -1; // The flag bit of the deletion cannot be repeated
expectedModCount = modCount;// Update the flag to determine whether the collection is modified.
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}// Determine if the List structure has been modified, if so, throw an exception
final void checkForComodification() {
if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the codeconclusion
- ModCount will be modified when modCount is deleted and modCount will be modified when modCount is deleted. ModCount is definitely not modified by modCount.
- Expansion leads to array replication, bulk deletion leads to finding the intersection of two collections, and array replication, so add and delete are relatively inefficient. And change, check is very efficient operation.
- Therefore, combined with the characteristics, in use, take the most commonly used display list in Android as an example. When the list is sliding, the array of each Item (Element) needs to be displayed, so the search operation is the highest frequency. In contrast, increment operations are only used when the list is loaded more and are inserted at the end of the list, so there is no need to move data. Deletion is much lower frequency. Therefore, ArrayList is chosen as the structure to save data