Basic attributes
An ArrayList uses an array to store elements, and its implementation is simple, with only two basic properties.
/** * an array that stores elements. When size equals the length of the array, it needs to be expanded */
transient Object[] elementData;
/** * The number of elements to store. = elementData.length */
private int size;
Copy the codeAarryList provides three constructors.
/** * specifies the array size */
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); }}/** * The initial array size is 0, and the array is expanded to 10 */ on the first insertion
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/** * construct */ from other collections
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if((size = a.length) ! =0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else{ elementData = Arrays.copyOf(a, size, Object[].class); }}else {
// replace with empty array.elementData = EMPTY_ELEMENTDATA; }}Copy the codeElement operation
Insert elements
When you insert an element, when size == elementData.length, you need to expand, so let’s look at expanding.
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
return grow(size + 1);
}
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); }private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
Copy the codeCapacity expansion actually copies the contents of the old array to the new array using the System. arrayCopy method. The size logic for the new array length is as follows:
- Normally, the new array is 1.5 times the length of the original array (
oldCapacity + (oldCapacity >> 1)) - Initially, the array size is expanded to 10 (default)
- The maximum array length is
Integer.MAX_VALUE
Moving on to insert elements, ArrayList provides two ways to insert individual elements.
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
/** * the element is inserted at the end of the array */
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
/** * inserts the element */ at the specified position
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code- The element is inserted at the end of the array. First determine whether to expand, and then give
elementData[size]Assignment, the time complexity is zeroO(1). - The element is inserted at the specified position. First determine whether the specified position is out of bounds (
[0, size]), then determine whether the capacity needs to be expanded, and then[index, size - 1]The element moves to[index + 1, size]Here is throughSystem.arraycopyCopies the elements of the specified range directly, faster than the loop, and finally giveselementData[index]The assignment.
As you can see, inserting elements in the middle is less efficient than inserting elements at the end, so try not to insert elements in the middle when using. ArrayList also provides methods for bulk inserts.
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
Copy the code- Insert at the end of the array. The first step is to determine whether to expand the array by adding the number of original elements and the number of newly added elements, and then add the newly added elements to the end of the array by batch copying.
- Insert at the specified position. First determine whether the specified position is out of bounds (
[0, size]), and then determine whether the capacity needs to be expanded, and then copy the array[index, size)The element moves to[index + newNum, size + newNum)The last element to be added is copied to[index, index + newNum].
Remove elements
/** * removes the element */ at the specified position
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
/** * deletes the specified element */
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
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 void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
Copy the codeWhen deleting a specified element, locate the subscript of the element before deleting it. Removes the element at the specified position by moving all elements after the specified position forward one bit, then setting the last element at the specified position to NULL, and changing size. ArrayList provides a way to delete elements in bulk.
/** * delete the element */ contained in set c
public boolean removeAll(Collection
c) {
return batchRemove(c, false.0, size);
}
/** ** select * from c
public boolean retainAll(Collection
c) {
return batchRemove(c, true.0, size);
}
boolean batchRemove(Collection<? > c,boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
if(c.contains(es[r]) ! = complement)break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
Copy the codeThe first loop determines the initial subscript of the element to be removed, then moves elements in elementData based on conditions (the second loop), and finally sets subsequent values to NULL (shiftTailOverGap). Since JDK8, ArrayList also provides the ability to delete elements that meet specified criteria and modify all elements to meet specified requirements.
/** * Removes the element */ that meets the specified criteria
@Override
public boolean removeIf(Predicate<? super E> filter) {
return removeIf(filter, 0, size);
}
boolean removeIf(Predicate<? super E> filter, int i, final int end) {
Objects.requireNonNull(filter);
int expectedModCount = modCount;
final Object[] es = elementData;
// Optimize for initial run of survivors
for(; i < end && ! filter.test(elementAt(es, i)); i++) ;// Tolerate predicates that reentrantly access the collection for
// read (but writers still get CME), so traverse once to find
// elements to delete, a second pass to physically expunge.
if (i < end) {
final int beg = i;
final long[] deathRow = nBits(end - beg);
deathRow[0] = 1L; // set bit 0
for (i = beg + 1; i < end; i++)
if (filter.test(elementAt(es, i)))
setBit(deathRow, i - beg);
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
modCount++;
int w = beg;
for (i = beg; i < end; i++)
if (isClear(deathRow, i - beg))
es[w++] = es[i];
shiftTailOverGap(es, w, end);
return true;
} else {
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
return false; }}private static long[] nBits(int n) {
return new long[((n - 1) > >6) + 1];
}
private static void setBit(long[] bits, int i) {
bits[i >> 6] | =1L << i;
}
private static boolean isClear(long[] bits, int i) {
return (bits[i >> 6] & (1L << i)) == 0;
}
/** * replaces the element */ as specified
@Override
public void replaceAll(UnaryOperator<E> operator) {
replaceAllRange(operator, 0, size);
modCount++;
}
private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final Object[] es = elementData;
for (; modCount == expectedModCount && i < end; i++)
es[i] = operator.apply(elementAt(es, i));
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
/** * replaces the element */ at the specified position
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the code- Delete the elements that meet the requirements. First determine the subscript of the first element that meets the requirements, then traverse the number group to find the subscript of the element to be deleted, which is recorded through the bitmap, then traverse again to delete the corresponding element (similar to the batch deletion there), and finally set the element in the additional position as
null. - It’s easy to replace all the elements as required, just go through the list and replace the elements.
Here’s an example:
public static void main(String[] args) {
int size = 10;
List<Integer> list = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
list.add(i);
}
list.removeIf(i -> i > 5);
System.out.println(list);
list.replaceAll(i -> i + 5);
System.out.println(list);
}
Copy the codeThe output is:
[0, 1, 2, 3, 4, 5]
[5, 6, 7, 8, 9, 10]
Copy the codeAccess to the elements
Accessing elements is simple, with subscripts, O(1) time.
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeThere are also simple methods to determine whether the collection contains elements and to query the subscripts of elements in the collection.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
returni; }}}else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
returni; }}}return -1;
}
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--) {
if (es[i] == null) {
returni; }}}else {
for (int i = end - 1; i >= start; i--) {
if (o.equals(es[i])) {
returni; }}}return -1;
}
Copy the codeother
equals
public boolean equals(Object o) {
if (o == this) {
return true;
}
if(! (oinstanceof List)) {
return false;
}
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
booleanequal = (o.getClass() == ArrayList.class) ? equalsArrayList((ArrayList<? >) o) : equalsRange((List<? >) o,0, size);
checkForComodification(expectedModCount);
return equal;
}
boolean equalsRange(List<? > other,int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
var oit = other.iterator();
for (; from < to; from++) {
if(! oit.hasNext() || ! Objects.equals(es[from], oit.next())) {return false; }}return! oit.hasNext(); }private boolean equalsArrayList(ArrayList
other) {
final int otherModCount = other.modCount;
final int s = size;
boolean equal;
if (equal = (s == other.size)) {
final Object[] otherEs = other.elementData;
final Object[] es = elementData;
if (s > es.length || s > otherEs.length) {
throw new ConcurrentModificationException();
}
for (int i = 0; i < s; i++) {
if(! Objects.equals(es[i], otherEs[i])) { equal =false;
break;
}
}
}
other.checkForComodification(otherModCount);
return equal;
}
private void checkForComodification(final int expectedModCount) {
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the codeAs you can see, except arrayLists can be compared to each other, any class that implements the List interface can be compared to An ArrayList, as long as the elements are stored in the same order and value, they are equal. The rest of the classes that implement the List interface override equals.
hashcode
public int hashCode(a) {
int expectedModCount = modCount;
int hash = hashCodeRange(0, size);
checkForComodification(expectedModCount);
return hash;
}
int hashCodeRange(int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
Copy the codeAs you can see, ArrayList computes HashCode by the elements it stores, so you should generally not use ArrayList as a key of a HashMap, or an element of a HashSet.
serialization
In ArrayList, its elementData attribute is preceded by the transient keyword, which means that elementData will not be serialized, but ArrayList has custom writeObject and readObject methods, Implementation of elementData serialization and deserialization logic.
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// like clone(), allocate array based upon size not capacity
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
Object[] elements = new Object[size];
// Read in all elements in the proper order.
for (int i = 0; i < size; i++) {
elements[i] = s.readObject();
}
elementData = elements;
} else if (size == 0) {
elementData = EMPTY_ELEMENTDATA;
} else {
throw new java.io.InvalidObjectException("Invalid size: "+ size); }}Copy the codeAs for the reason for customization, my understanding is that elementData is a dynamic array that may hold many NULL elements, so the serialization logic is customized to avoid serializing unnecessary elements.
The iterator
ArrayListCustom iterators that can iterate through elements in both directions (next,previous).ArrayListtheforeachThe loop is actually accessed through iterators, and you can decompile the compiled code, as you can see.
/ / the original code
List<Integer> list = new ArrayList<>();
for (Integer i : list) {
System.out.println(i);
}
// The compiled code
List<Integer> list = new ArrayList();
Iterator var2 = list.iterator();
while(var2.hasNext()) {
Integer i = (Integer)var2.next();
System.out.println(i);
}
Copy the codeSo, accessed through the foreach element, don’t modify ArrayList and if the value of the modified modCount would throw ConcurrentModificationException.
public E next(a) {
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();
}
Copy the codeconclusion
ArrayListIt’s actually a dynamic array that can be addednullElement, which is non-thread-safe.ArrayListthehashcodeThe value changes as the element it stores changes.ArrayListNon-tail insertion and non-tail deletion consume a lot and should be used as little as possible. During initialization, specify the capacity as much as possible to reduce capacity expansion times.