I read a sentence before, and it was very good. Someone asked what the use of reading source code is? Learn the design ideas of others to implement a certain function and improve your programming level.
Yes, everyone implements a function. Different people have different design ideas. Some people use 10,000 lines of code, and some people use 5,000 lines. Some people need to run the code for dozens of seconds, while others only need a few seconds. . Let’s get to the topic below.
Main content of this article:
・A detailed comment on the implementation of ArrayList, based on JDK 1.8.
・The iterator SubList part has not been explained in detail, and will be placed in other source code interpretations. Here we focus on the implementation of ArrayList itself.
・No standard annotations are used, and the indentation of the code is adjusted appropriately for easy introduction
import java.util.AbstractList;import java.util.Arrays;import java.util.BitSet;import java.util.Collection;import java.util.Comparator;import java.util.ConcurrentModificationException;import java.util.Iterator;import java.util.List;import java.util.ListIterator;import java.util.NoSuchElementException;import java.util.Objects;import java.util.RandomAccess;import java.util.Spliterator;import java.util.function.Consumer;import java.util.function.Predicate;import java.util.function.UnaryOperator;/** * Overview: * An array implementation of the List interface that can be resized. Implement all optional List operations and allow all elements, including null, to be repeatable. * In addition to the list interface, this class provides a way to manipulate the size of the array to store the size of the array in the list. * * Time complexity: * The calls to methods size, isEmpty, get, set, iterator and listIterator are constant time. * The time complexity of adding and deleting is O(N). All other operations are linear time complexity. * * Capacity: * Each ArrayList has capacity, and the capacity size is at least the length of the List element, and the default initialization is 10. * Capacity can be automatically increased. * If you know in advance that there are many elements in the array, you can increase the capacity in advance by calling the ensureCapacity() method before adding elements to reduce the overhead of automatic capacity growth in the later period. * This capacity can also be initialized by a constructor with initial capacity. * * Thread is not safe: * ArrayList is not thread safe. * If it needs to be applied to multithreads, synchronization needs to be done externally * * modCount: * Defined in AbstractList: protected transient int modCount = 0; * Number of times this list has been modified structurally. Structural modification refers to changing the size of the list, or disrupting the list, so that the ongoing iteration produces incorrect results. * This field is used by the iterator and list iterator implementations returned by the iterator and listerator methods. * If the value in this field is accidentally changed, the iterator (or list iterator) will throw a concurrentmodificationexception in response to next, remove, previous, set, or add operations. * When faced with concurrent modifications during iterations, it provides fast failed behavior rather than non-deterministic behavior. * Whether the subclass uses this field is optional. * If the subclass wishes to provide a fast fail iterator (and list iterator), it simply adds this field to its add(int,e) and remove(int) methods (and any other methods it overrides, resulting in modifications on the list structure). * The number of single calls to add(int, e) or remove(int) must not exceed 1 to this field, otherwise the iterator (and list iterator) will throw fake concurrentmodificationexceptions. * If an implementation does not want to provide a fast fail iterator, this field can be ignored. * * transient: * By default, all member variables of an object will be persisted. In some cases, if you want to avoid persisting some member variables of an object, you can use the transient keyword to tag them, which is also a reserved word in java (JDK 1.8) */public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ private static final long serialVersionUID = 8683452581122892189L; //Default initial capacity private static final int DEFAULT_CAPACITY = 10; // Used to share empty array instances with empty instances. private static final Object[] EMPTY_ELEMENTDATA = {}; //Default empty array private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //For the right, the array of elements, package access permissions are stored transient Object[] elementData; //Size, Java will initialize int to 0 when creating an object private int size; //Set the constructor of the initialization capacity with the specified number, and the negative number will throw an exception 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); } } //Default constructor, use control array to initialize public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //Construct a list containing elements in the collection in the order of the iterator return of the collection public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toarray may (error) not return object[] (see JAVA BUG number 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // Use an empty array this.elementData = EMPTY_ELEMENTDATA; } } //Because the capacity is often greater than the actual number of elements. When memory is tight, you can call this method to delete the reserved location and adjust the capacity to the actual number of elements. //If you are sure that no elements will be added, you can also call this method to save space public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //Set array capacity with specified parameters public void ensureCapacity(int minCapacity) { //If the array is empty, prefetch 0, otherwise go to the default value (10) int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY; //If the parameter is greater than the preset capacity, use this parameter to further set the array capacity if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } //When adding elements, ensure the array capacity private void ensureCapacityInternal(int minCapacity) { //Use the default value and the larger parameter as the capacity preset value if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } //If the parameter is greater than the array capacity, increase the array capacity private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); } //The maximum capacity of the array may cause memory overflow (VM memory limit) private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //Increase the capacity to ensure that it can hold at least the number of elements specified by the parameter private void grow(int minCapacity) { int oldCapacity = elementData.length; //Increase the preset capacity by half int newCapacity = oldCapacity + (oldCapacity >> 1); //Take the larger value from the parameter if (newCapacity - minCapacity < 0)//That is, newCapacity<minCapacity newCapacity = minCapacity; //If the preset value is greater than the default maximum, check whether it overflows if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } //Check whether it overflows. If there is no overflow, return the maximum integer value (the int in java is 4 bytes, so the maximum is 0x7ffffffff) or the default maximum value private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) //Overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } //Return the array size public int size() { return size; } //Is it empty public boolean isEmpty() { return size == 0; } //Whether it contains a number, return bool public boolean contains(Object o) { return indexOf(o) >= 0; } //Return a value at the first appearance of the array, and it will be judged in different ways based on whether it is null. If it does not exist, it returns -1. The time complexity is O(N) 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; } //Return a value at the last time when it appears in the array. If it does not exist, it returns -1. Time complexity is O(N) public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } //Return the copy, the element itself has not been copied, and an exception will be thrown when the array of the copying process changes public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { throw new InternalError(e); } } //Convert to an Object array, use the Arrays.copyOf() method public Object[] toArray() { return Arrays.copyOf(elementData, size); } //Return an array, use the runtime to determine the type, and the array contains all elements in this list (from the first to the last element) //The returned array capacity is determined by the parameters and the larger value in this array @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } //Return the value of the specified position, because it is an array, it is particularly fast @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } //Return the value of the specified position, but check whether the number of positions exceeds the array length public E get(int index) { rangeCheck(index); return elementData(index); } //Set the specified position to a new value and return the previous value, check whether this position exceeds the array length public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } //Add a value first ensures the capacity public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } //Add a value in the specified position and check the added position and capacity public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) //src: Source array; srcPos: The starting position of the source array to be copied; dest: destination array; destPos: The starting position of the destination array; length:copy length System.arraycopy(elementData, index, elementData, index + 1,size - index); elementData[index] = element; size++; } //Delete the value of the specified position, check the added position and return the previous value public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,numMoved); elementData[--size] = null; //Easy to recycle the garbage collection period return oldValue; } //Delete the location where the specified element first appears public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } //Quickly delete the value at the specified position. The reason why it is called fast should be that there is no need to check and return the value, because only private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,numMoved); elementData[--size] = null; // clear to let GC do its work } //Clear the array and set each value to null to facilitate garbage collection (unlike reset, the default size of the array will not be reset if it changes) public void clear() { modCount++; for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } //Add an element of a collection to the end, if the collection to be added is empty, return false public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } //The function is the same as above, add public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); //The array to be added int numNew = a.length; //The length of the array to be added ensureCapacityInternal(size + numNew); //Ensure capacity int numMoved = size - index;//The length that will not move (the previous part) if (numMoved > 0) //If there is no need to move, copy it by itself and move the back part of the array to the correct position System.arraycopy(elementData, index, elementData, index + numNew,numMoved); System.arraycopy(a, 0, elementData, index, numNew); //Add new array to the middle of the changed original array size += numNew; return numNew != 0; } //Delete the specified range element. The parameters are the starting and ending positions protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; //The length retained by the latter section System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } //Check if the number exceeds the length of the array when adding elements private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //Check whether private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //Details of the thrown exception private String outOfBoundsMsg(int index)) { return "Index: "+index+", Size: "+size; } //Delete the element of the specified collection public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c);//Check whether the parameter is null return batchRemove(c, false); } //Retain only the elements of the specified collection public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } /** * Source code interpretation BY http://anxpp.com/ * @param complete When true, the value of the element in the specified collection is retained from the array, and when false, the value of the element in the specified collection is deleted from the array. * @return The duplicate elements in the array will be deleted (rather than just deleted once or several times), and any deletion operation will return true */ private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { //Transweep through the array and check whether this collection contains the corresponding value, move the value to be retained to the front of the array, and the last value of w is the number of elements to be retained//Simple point: if retained, move the same element to the previous section; if deleted, move different elements to the previous section for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally {//Make sure that the part before the exception is thrown can complete the expected operation, while the part that has not been traversed will be connected to the back //r!=size means that an error may occur: c.contains(elementData[r]) throws an exception if (r != size) { System.arraycopy(elementData, r,elementData, w,size - r); w += size - r; } //If w==size: means that all elements are retained, so no delete operation occurs, so false will be returned; otherwise, true and the array // When w!=size is returned, even if the try block throws an exception, the operation before the exception is thrown, because w is always the length of the previous part to be retained, and the array will not be out of order because (w != size) { for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w;//The number of times changed size = w; //The new size is the number of elements preserved modified = true; } } return modified; } //Save the state of the array instance to a stream (that is, it is serialized). The write process array is changed and an exception will be thrown private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ int expectedModCount = modCount; s.defaultWriteObject(); //Execute the default deserialization/serialization process. Write non-static and non-transitory fields of the current class to this stream // Write to size s.writeInt(size); // Write all elements in order for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } //The above is written, this is read. private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Perform the default serialization/deserialization process s.defaultReadObject(); // Read in the array length s.readInt(); if (size > 0) { ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements for (int i=0; i<size; i++) { a[i] = s.readObject(); } } } } //Return ListIterator, the starting position is the specified parameter public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } //Return ListIterator, the starting position is 0 public ListIterator<E> listIterator() { return new ListItr(0); } //Return ordinary iterator public Iterator<E> iterator() { return new Itr(); } //The general iterator implements private class Itr implements Iterator<E> { int cursor; //The cursor, the index of the next element, the default initialization is 0 int lastRet = -1; //The position of the last accessed element is int expectedModCount = modCount;//The iteration process does not run the modified array, otherwise an exception will be thrown//Is there another public boolean hasNext() { return cursor != size; } //The next element @SuppressWarnings("unchecked") public E next() { checkForComodification();//Check whether the array is modified int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; //Move the cursor backwards return (E) elementData[lastRet = i]; //Set the access position and return this value} //Delete the element public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification();//Check whether the array is modified try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } cursor = i; lastRet = i - 1; checkForComodification(); } //Check whether the array is modified final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } //ListIterator iterator implements private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { super(); cursor = index; } public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } //Return subarray of the specified range public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); } //Security check static void subListRangeCheck(int fromIndex, int toIndex, int size) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); if (toIndex > size) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } //Subarray private class SubList extends AbstractList<E> implements RandomAccess { private final AbstractList<E> parent; private final int parentOffset; private final int offset; int size; SubList(AbstractList<E> parent,int offset, int fromIndex, int toIndex) { this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } public E set(int index, E e) { rangeCheck(index); checkForComodification(); E oldValue = ArrayList.this.elementData(offset + index); ArrayList.this.elementData[offset + index] = e; return oldValue; } public E get(int index) { rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); } public int size() { checkForComodification(); return this.size; } public void add(int index, E e) { rangeCheckForAdd(index); checkForComodification(); parent.add(parentOffset + index, e); this.modCount = parent.modCount; this.size++; } public E remove(int index) { rangeCheck(index); checkForComodification(); E result = parent.remove(parentOffset + index); this.modCount = parent.modCount; this.size--; return result; } protected void removeRange(int fromIndex, int toIndex) { checkForComodification(); parent.removeRange(parentOffset + fromIndex,parentOffset + toIndex); this.modCount = parent.modCount; this.size -= toIndex - fromIndex; } public boolean addAll(Collection<? extends E> c) { return addAll(this.size, c); } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); int cSize = c.size(); if (cSize==0) return false; checkForComodification(); parent.addAll(parentOffset + index, c); this.modCount = parent.modCount; this.size += cSize; return true; } public Iterator<E> iterator() { return listIterator(); } public ListIterator<E> listIterator(final int index) { checkForComodification(); rangeCheckForAdd(index); final int offset = this.offset; return new ListIterator<E>() { int cursor = index; int lastRet = -1; int expectedModCount = ArrayList.this.modCount; public boolean hasNext() { return cursor != SubList.this.size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= SubList.this.size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[offset + (lastRet = i)]; } public boolean hasPrevious() { return cursor != 0; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[offset + (lastRet = i)]; } @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = SubList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (offset + i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[offset + (i++)]); } // update once at end of iteration to reduce heap write traffic lastRet = cursor = i; checkForComodification(); } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { SubList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = ArrayList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(offset + lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; SubList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = ArrayList.this.modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (expectedModCount != ArrayList.this.modCount) throw new ConcurrentModificationException(); } }; } public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, offset, fromIndex, toIndex); } private void rangeCheck(int index) { if (index < 0 || index >= this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void rangeCheckForAdd(int index) { if (index < 0 || index > this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+this.size; } private void checkForComodification() { if (ArrayList.this.modCount != this.modCount) throw new ConcurrentModificationException(); } public Spliterator<E> splitterator() { checkForComodification(); return new ArrayListSpliterator<E>(ArrayList.this, offset,offset + this.size, this.modCount); } } @Override public void forEach(Consumer<? super E> action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } /** * Creates a <em><a href="Spliterator.html#binding" rel="external nofollow" >late-binding</a></em> * and <em>fail-fast</em> {@link Spliterator} over the elements in this * list. * * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}. * Overriding implementations should document the reporting of additional * characteristic values. * * @return a {@code Spliterator} over the elements in this list * @since 1.8 */ @Override public Spliterator<E> splitterator() { return new ArrayListSpliterator<>(this, 0, -1, 0); } /** Index-based split-by-two, lazy initialized Spliterator */ static final class ArrayListSpliterator<E> implements Spliterator<E> { /* * If ArrayLists were immutable, or structurally immutable (no * adds, removes, etc), we could implement their splitterators * with Arrays.spliterator. Instead we detect as much * interference during traversal as practical without * sacrificing much performance. We rely primarily on * modCounts. These are not guaranteed to detect concurrency * violence, and are sometimes overly conservative about * within-thread interference, but detect enough problems to * be worthwhile in practice. To carry this out, we (1) lazily * initialize fence and expectedModCount until the latest * point that we need to commit to the state we are checking * against; thus improving precision. (This doesn't apply to * SubLists, that create splitterators with current non-lazy * values). (2) We perform only a single * ConcurrentModificationException check at the end of forEach * (the most performance-sensitive method). When using forEach * (as opposed to iterators), we can normally only detect * interference after actions, not before. Further * CME-triggering checks apply to all other possible * violence of assumptions for example null or too-small * elementData array given its size(), that could only have * occurred due to interference. This allows the inner loop * of forEach to run without any further checks, and * simplifies lambda-resolution. While this does entail a * number of checks, note that in the common case of * list.stream().forEach(a), no checks or other computing * occurs anywhere other than inside forEach itself. The other * less-often-used methods cannot take advantage of most of * these streamlinings. */ private final ArrayList<E> list; private int index; // current index, modified on advance/split private int fence; // -1 until used; then one past last index private int expectedModCount; // initialized when fence set /** Create new spliterator covering the given range */ ArrayListSpliterator(ArrayList<E> list, int origin, int fence, int expectedModCount) { this.list = list; // OK if null unless traversed this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; } private int getFence() { // initialize fence to size on first use int hi; // (a specialized variant appears in method forEach) ArrayList<E> lst; if ((hi = fence) < 0) { if ((lst = list) == null) hi = fence = 0; else { expectedModCount = lst.modCount; hi = fence = lst.size; } } return hi; } public ArrayListSpliterator<E> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : // divide range in half unless too small new ArrayListSpliterator<E>(list, lo, index = mid, expectedModCount); } public boolean tryAdvance(Consumer<? super E> action) { if (action == null) throw new NullPointerException(); int hi = getFence(), i = index; if (i < hi) { index = i + 1; @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } public void forEachRemaining(Consumer<? super E> action) { int i, hi, mc; // hoist accesses and checks from loop ArrayList<E> lst; Object[] a; if (action == null) throw new NullPointerException(); if ((lst = list) != null && (a = lst.elementData) != null) { if ((hi = fence) < 0) { mc = lst.modCount; hi = lst.size; } else mc = expectedModCount; if ((i = index) >= 0 && (index = hi) <= a.length) { for (; i < hi; ++i) { @SuppressWarnings("unchecked") E e = (E) a[i]; action.accept(e); } if (lst.modCount == mc) return; } } throw new ConcurrentModificationException(); } public long estimateSize() { return (long) (getFence() - index); } public int characteristics() { return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } } @Override public boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); // figure out which elements are to be removed // any exception thrown from the filter predicted at this stage // will leave the collection unmodified int removeCount = 0; final BitSet removeSet = new BitSet(size); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { @SuppressWarnings("unchecked") final E element = (E) elementData[i]; if (filter.test(element)) { removeSet.set(i); removeCount++; } } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } // shift surviving elements left over the spaces left by removed elements final boolean anyToRemove = removeCount > 0; if (anyToRemove) { final int newSize = size - removeCount; for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { i = removeSet.nextClearBit(i); elementData[j] = elementData[i]; } for (int k=newSize; k < size; k++) { elementData[k] = null; // Let gc do its work } this.size = newSize; if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } return anyToRemove; } @Override @SuppressWarnings("unchecked") public void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { elementData[i] = operator.apply((E) elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } @Override @SuppressWarnings("unchecked") public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }}Summarize
以上就是本文关于Java编程中ArrayList源码分析的全部内容，希望对大家有所帮助。 Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!