JDK version: 13
1 class diagram
1.1 Interface Implementation
java.util.List: Provides basic operations such as add, delete, modify, and checkjava.io.Serializable: marks the interface to support serializationjava.lang.Cloneable: marks the interface to support cloningjava.util.RandomAccessThis interface may not be noticed, but it is also a tag interface that represents the ability to randomly access elements, which is simply a collection of array implementations. Reference:What is RandomAccess for?
1.2 inheritance
java.util.AbstractListAbstract class, which, as you can see from the comments, provides the basic implementation of the List interface to minimize the implementation of iterating through related operations. But ArrayList basically overrides the implementation provided by AbstractList.
2 attribute
int elementData: The true size of an array that stores elementsint size:elementDataThe actual number of elements stored in thesize()That’s what the method returns
3. Construction Method
3.1 ArrayList(int initialCapacity)
/** * an empty array to which elementData is pointed when initialized to 0 */
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
// Create an Object array with a capacity greater than 0
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// equals 0 using EMPTY_ELEMENTDATA
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
< 0 throws an exception
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the codeUsing this method to create an ArrayList, we can use memory reasonably and avoid the performance cost of array expansion.
3.2 ArrayList()
/** * Default initial capacity. */
private static final int DEFAULT_CAPACITY = 10;
/** * An empty array when the default capacity is used. When using no-argument construction, elementData is initialized to an array of length 10 only when the element is first added, in order to save memory (considering the case where an ArrayList object is created but not used) *. * distinguish it from EMPTY_ELEMENTDATA so that when you initialize it, you know that you are directly initialized to 10. * EMPTY_ELEMENTDATA starts at 0 and expands by 1.5 times. * /
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * create ArrayList */ with default capacity 10
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code3.3 ArrayList(Collection<? extends E> c)
/** * pass in a collection to create ArrayList */
public ArrayList(Collection<? extends E> c) {
// Turn the collection into an Object array
elementData = c.toArray();
// If the array length is not equal to 0
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 is not an Object array type, create a new Object array,
// Assign elements from elementData, and finally assign the new array to elementData
C. toarray does not return an array of type Ojbect[]
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class);// If the array size is 0, use EMPTY_ELEMENTDATA
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
/ /?? Why use this.elementData and not use this? the
}
Copy the code4 Main Methods
4.1 Adding an element
boolean add(E e)Add to tail
/** * adds an element to the end */
public boolean add(E e) {
< AbstractList > < AbstractList > < AbstractList > < AbstractList
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
// If the capacity is insufficient, expand the capacity
if (s == elementData.length)
elementData = grow();
// Put the element at the end of the array
elementData[s] = e;
// size +1
size = s + 1;
}
Copy the codevoid add(int index, E element)Adds to the specified location
/** * inserts an element */ at the specified position
public void add(int index, E element) {
// Check if index is in array range
rangeCheckForAdd(index);
// Number of changes +1
modCount++;
final int s;
Object[] elementData;
// If the capacity is insufficient, expand the capacity
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// Move the index position and the element after it one bit back
// Array copy
System.arraycopy(elementData, / / the original array
index, // From the beginning of the original array
elementData, // Target array
index + 1.// At the beginning of the destination array
s - index); // The number of elements to copy
// Place the insert element at index
elementData[index] = element;
// size + 1
size = s + 1;
}
Copy the code4.2 capacity
Object[] grow()
private Object[] grow() {
// The capacity after expansion must be at least 1 larger than before
return grow(size + 1);
}
/ * * *@paramMinCapacity Minimum capacity required after capacity expansion */
private Object[] grow(int minCapacity) {
// Record the old capacity
int oldCapacity = elementData.length;
// If the capacity is greater than 0 or the array is not DEFAULTCAPACITY_EMPTY_ELEMENTDATA, calculate the new capacity and expand it
if (oldCapacity > 0|| elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth Minimum growth */
oldCapacity >> 1 /* Preferred growth */);
// Copy the elements into the new array
return elementData = Arrays.copyOf(elementData, newCapacity);
/* arrayssupport. newLength calculates the new array size by taking the larger values of minimum growth and preferred Growth plus the old size. It also involves some checksum handling of the maximum length of an array, which I won't go into here. >> is the shift operator, so moving one bit to the right is the same as dividing by two, which means we're scaling up to 1.5 times. If we're scaling up from 0, 0 >> 1 is still 0, and we're using minCapacity, which is 1 */
// Create a new array if DEFAULTCAPACITY_EMPTY_ELEMENTDATA
} else {
// Take the default capacity and the larger values in minCapacity
return elementData = newObject[Math.max(DEFAULT_CAPACITY, minCapacity)]; }}Copy the code4.3 Adding Multiple Elements
boolean addAll(Collection<? extends E> c)Add to the end
/** * Add multiple elements to the end * Calling this method avoids multiple array expansions compared to adding elements one by one */
public boolean addAll(Collection<? extends E> c) {
// Convert to an array
Object[] a = c.toArray();
// Number of changes +1
modCount++;
// Number of new elements added
int numNew = a.length;
// If the number is 0, return false. The ArrayList has not changed, but the number of changes has increased
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// If there is not enough space for the new elements, expand the capacity to at least accommodate the new data
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
// Copy the new array into the end of elementData
System.arraycopy(a, 0, elementData, s, numNew);
// Calculate the size
size = s + numNew;
return true;
}
Copy the codeboolean addAll(int index, Collection<? extends E> c)Adds to the specified location
public boolean addAll(int index, Collection<? extends E> c) {
// Check for overbounds
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// At least the new array will fit
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
// If the index position already has elements, move its beginning and subsequent elements back out of position
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
// Add the new array to the location specified by elementData
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
Copy the code4.4 Removing a Single element
E remove(int index)Removes the element at the specified position and returns the element
public E remove(int index) {
// Check index cannot > size
Objects.checkIndex(index, size);
final Object[] es = elementData;
// Record the deleted value
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
// Returns the deleted value
return oldValue;
}
/** * The core logic responsible for the deletion does not care about returning the deleted element or checking out of bounds */
private void fastRemove(Object[] es, int i) {
// Number of changes +1
modCount++;
final int newSize;
// size is 1 larger than the subscript. Size -1 is the last digit of the array
// If not the last digit, move all elements after I one digit forward.
if ((newSize = size - 1) > i) // Note the hidden size-1 operation
System.arraycopy(es, i + 1, es, i, newSize - i);
// Leave the last position empty to help GC
es[size = newSize] = null;
}
Copy the codeboolean remove(Object o)Remove the first one asoElement, returns whether to remove
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
// Used to mark the location of the first o found
int i = 0;
found: { // Use break to terminate block execution to make code more concise
// If o is null
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
// If o is not null
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
/ / remove
fastRemove(es, i);
return true;
}
Copy the code4.5 Removing Multiple elements
boolean removeAll(Collection<? > c)If the element is in set C, it’s removed
/** * delete multiple elements */
public boolean removeAll(Collection
c) {
// The batch delete method was called
return batchRemove(c, false.0, size);
}
Copy the codeboolean batchRemove(Collection<? > c, boolean complement, final int from, final int end)Remove or retain elements in batches
It’s a little convoluted. Let’s start with the parameter complement, which states whether an element in set C remains or is deleted. Public Boolean retainAll(Collection
c) { return batchRemove(c, true, 0, size); } is easy to understand. When complement is false, it is the logic to remove. And true is the intersection of two sets.
The general logic of this method is to find the index of the first element to be removed, denoting it as w, and its next digit as r. If it’s an element you want to delete, you skip it. If it’s an element you want to keep, you write it to where W is, overwrite the previous element, and move w one place down to continue the loop. Finally, null any unwanted elements at the end of the array. I have posted a sketch of the code below, which can be combined to understand. Or debug debugging several times.
/** * Delete or retain multiple elements * in batches@paramC Set of elements to be deleted *@paramComplement if an element in C, delete or retain *@paramFrom start position *@paramEnd Indicates the end position *@return* /
boolean batchRemove(Collection<? > c,boolean complement,
final int from, final int end) {
// check that c is not null
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivor
// I want to see if there is an element in C in elementData on the delete logic front, but I don't want to iterate
// Find the position r where the first element that does not match complement completes the loop
for (r = from;; r++) {
if (r == end)
return false;
if(c.contains(es[r]) ! = complement)break;
}
// w marks the position of r, with r + 1 pointing to the next position
int w = r++; // Note that this is equivalent to w = r; r = r + 1; (Difference between I ++ and ++ I)
try {
for (Object e; r < end; r++)
// If the element of position R is complement, write the element of position r to the element of position w
// If not, w does not move and carries on the next loop
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// If the cntains() method throws an exception, write data after r to w
// So that we can move over the untraversed elements and overwrite the skipped elements, ensuring that there are no more strange elements in the array
System.arraycopy(es, r, es, w, end - r);
w += end - r;
// Continue to throw the exception
throw ex;
} finally {
// Increase the number of changes
modCount += end - w;
// Assign null to tail useless elements
shiftTailOverGap(es, w, end);
}
return true;
}
/** * Make a cut in the array hi and lo, drop the part between hi and lo, and connect hi to lo **@param* es array@paramLo start position *@paramHi end position */
private void shiftTailOverGap(Object[] es, int lo, int hi) {
// The element starting at hi is moved to LO
System.arraycopy(es, hi, es, lo, size - hi);
// Empty the unused space at the end
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
Copy the code
Batch removes multiple elements within a given rangevoid removeRange(int fromIndex, int toIndex)
/** * Batch removes multiple elements from fromIndex (front closed, back open) */
protected void removeRange(int fromIndex, int toIndex) {
// The parameter is incorrect
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
// Number of changes +1
modCount++;
// See above for the method
shiftTailOverGap(elementData, fromIndex, toIndex);
}
Copy the codeRemove elements based on conditionsboolean removeIf(Predicate<? super E> filter)
A little…
4.6 Searching for an Element
int indexOf(Object o)Finds the index of the first specified element
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
// o is null
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
returni; }}O is not null
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
returni; }}}// Return -1 if not found
return -1;
}
Copy the codeint indexOf(Object o)Finds the index of the last specified element
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}
int lastIndexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = end - 1; i >= start; i--) { / / reverse
if (es[i] == null) {
returni; }}}else {
for (int i = end - 1; i >= start; i--) {
if (o.equals(es[i])) {
returni; }}}return -1;
}
Copy the codeint indexOf(Object o)Gets the element at the specified position
public E get(int index) {
/ / check
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the code4.7 Setting the element at the specified position
E set(int index, E element)
public E set(int index, E element) {
/ / check
Objects.checkIndex(index, size);
// Record the old value
E oldValue = elementData(index);
// Assign a new value
elementData[index] = element;
// Return the old value
return oldValue;
}
Copy the code5 Other Methods
5.1 Converting to an array
Object[] toArray()Convert the Object []
// ArrayList.java
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// Arrays.java
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
Copy the codeObject[] toArray()To an array of the given generic type
public <T> T[] toArray(T[] a) {
// If the array size passed is not as large as size
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
// Copy a new array directly
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// Copy elementData into a
System.arraycopy(elementData, 0, a, 0, size);
// If the length of a is greater than size, then. Set the size position to null.
if (a.length > size)
a[size] = null;
return a;
}
Copy the codeA [size] = null; a[size] = null;
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
* {@code null}. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
Copy the codeIf the caller knows explicitly that there are no empty elements in the array, it helps to determine the length of the list. emmm… Insert null value as a flag.. Perhaps the caller could decide that the element was empty while iterating through the array and not iterate again?
5.2 Finding the hash value
int hashCode()
public int hashCode(a) {
// Record the number of changes to the array before starting
int expectedModCount = modCount;
// Get the hash value
int hash = hashCodeRange(0, size);
// Modify the verification concurrently
checkForComodification(expectedModCount);
return hash;
}
int hashCodeRange(int from, int to) {
final Object[] es = elementData;
/ / check
if (to > es.length) {
throw new ConcurrentModificationException();
}
// Computes the hash value
int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
// Why multiply by 31? See resources below
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
/** * If the number of times the array has been modified before the operation is inconsistent with the number of times the array has been modified after the operation, an exception will be thrown */
private void checkForComodification(final int expectedModCount) {
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the codeWhy does the String hashCode method choose the number 31 as its multiplier
5.3 Determining equality
boolean equals(Object o)
public boolean equals(Object o) {
// Directly returns true compared to itself
if (o == this) {
return true;
}
// Non-list, return false
if(! (oinstanceof List)) {
return false;
}
// Count the number of changes to the current array
final int expectedModCount = modCount;
// ArrayList can be subclassed and given arbitrary behavior, but we can
// still deal with the common case where o is ArrayList precisely
// Select different comparison methods depending on whether the type is ArrayList
// ArrayList can iterate over arrays with better performance, whereas other lists can only use iterators.
booleanequal = (o.getClass() == ArrayList.class) ? equalsArrayList((ArrayList<? >) o) : equalsRange((List<? >) o,0, size);
// Modify the verification concurrently
checkForComodification(expectedModCount);
return equal;
}
private boolean equalsArrayList(ArrayList
other) {
// Records the number of changes passed to the list
final int otherModCount = other.modCount;
final int s = size;
boolean equal;
// Check whether the size is equal
if (equal = (s == other.size)) {
final Object[] otherEs = other.elementData;
final Object[] es = elementData;
// Verify concurrent modification
if (s > es.length || s > otherEs.length) {
throw new ConcurrentModificationException();
}
// Iterate over and compare the equality of each corresponding element
for (int i = 0; i < s; i++) {
if(! Objects.equals(es[i], otherEs[i])) { equal =false; // If not, break out of the loop
break; }}}// Validates concurrent changes to the passed list
other.checkForComodification(otherModCount);
return equal;
}
boolean equalsRange(List<? > other,int from, int to) {
final Object[] es = elementData;
// Modify the verification concurrently
if (to > es.length) {
throw new ConcurrentModificationException();
}
// Iterate over each comparison with an iterator
var oit = other.iterator();
for (; from < to; from++) {
// If oIT has no next element or the current element is not equal, return false
if(! oit.hasNext() || ! Objects.equals(es[from], oit.next())) {return false; }}// Returns whether oIT has any remaining elements. If there are, of course, they're not equal
return! oit.hasNext(); }Copy the code5.4 the cloning
Object clone()
public Object clone(a) {
try {
// Call the parent clone methodArrayList<? > v = (ArrayList<? >)super.clone();
// Copy the new array
v.elementData = Arrays.copyOf(elementData, size);
// Set the number of changes to 0
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
// The Cloneable interface will no longer occur
throw new InternalError(e); // JVM unexpected internal error}}Copy the code5.5 to empty
void clear()
public void clear(a) {
// Number of changes + 1
modCount++;
// iterate over empty reverse order
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
Copy the code5.6 Serialization and deserialization
void writeObject(java.io.ObjectOutputStream s)serialization
@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
int expectedModCount = modCount;
// Serialize non-static, non-transient attributes
s.defaultWriteObject();
// Write size to be compatible with the clone() method.
s.writeInt(size);
// Write out all elements in the proper order.
// Write elements one by one
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// Modify the verification concurrently
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the codeElementData is a transient keyword, serialization will only serialize the size of the actual use of the array, not the elementData reserved part of the serialization. Save time and space.
void readObject(java.io.ObjectOutputStream s)
@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Deserialize non-static, non-transient attributes
s.defaultReadObject();
// Read in capacity
// Read the size, but ignore it
s.readInt(); // ignored
if (size > 0) {
// like clone(), allocate array based upon size not capacity
// emmm....
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
Object[] elements = new Object[size];
// Read the elements one by one
for (int i = 0; i < size; i++) {
elements[i] = s.readObject();
}
elementData = elements;
} else if (size == 0) {
// use an empty array if size is 0
elementData = EMPTY_ELEMENTDATA;
} else {
throw new java.io.InvalidObjectException("Invalid size: "+ size); }}Copy the code6 End
Some uncommon or simple methods are omitted, as well as methods (such as sort() sort) that are not logically focused on the ArrayList.