Write in front: some notes to learn Java source code, JDK version 1.8.0_131
attribute
private static final long serialVersionUID = 8683452581122892189L; /** * Default initial capacity. */ / Private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used 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 [public args] [public args] [public args] to know how much to inflate when * first element is added. 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. */ / attributes that are modified by the keyword transient will be ignored during serialization. transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;Copy the codeThe constructor
1. ArrayList()
With no arguments, elementData points to an empty Object[] array
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code2. ArrayList(int initialCapacity)
A parameter constructor that passes in an integer and throws an exception if it is negative; An input of 0 points to an empty array of Object[], which is different from the address of the empty array in the no-argument constructor. If the input is greater than 0, an Object[] array of size is created.
/** * 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 code3. ArrayList(Collection<? extends E> c)
Takes a parameter construct and passes it as a Collection object.
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * 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) {// Convert a Collection object to an array via toArray() elementData = c.toarray (); If ((size = elementData.length)! ToArray () does not return an Object array. = 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); Empty array.this. elementData = EMPTY_ELEMENTDATA; // replace with empty array.this. elementData = EMPTY_ELEMENTDATA; }}Copy the codemethods
1. add(E e)
This method is used to add the specified element to the end of the ArrayList. The parameter is the added element and the return value is Boolean indicating whether the element was added successfully. Add (E E)
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public Boolean add(E E) ensureCapacityInternal(size + 1); // Increments modCount!! ElementData [size++] = e; return true; }Copy the codeThe method to confirm whether the array capacity is sufficient is as follows:
Private void ensureCapacityInternal(int minCapacity) {// Array is an empty array, Then change minCapacity from size + 1 (1) to the default value 10. // set minCapacity to a larger value than 10. DEFAULTCAPACITY_EMPTY_ELEMENTDATA // If (elementData ==) is not compared with the default value 10 DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) {private void ensureExplicitCapacity(int minCapacity) { // overflow-conscious code // minCapacity compared to the array size, if the required capacity is greater than the array size, If (mincapacity-elementdata. length > 0) grow(minCapacity); }Copy the codeCapacity expansion method:
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); // the newCapacity is 1.5 times the oldCapacity (this operation may cause int overflow). If (newCapacity - minCapacity < 0) newCapacity = minCapacity; // If the required capacity is larger than the maximum array size set by the system, Call hugeCapacity() if (newCapacity -max_array_size > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: ElementData = array.copyof (elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { If (minCapacity < 0) // Overflow throw new OutOfMemoryError(); Integer.MAX_VALUE, otherwise MAX_ARRAY_SIZE. Return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }Copy the codeIn the implementation of Add (E E), check whether the existing capacity needs to be expanded. If the capacity needs to be expanded, the rule is 1.5 times the original capacity. The size of the expanded array may exceed the allowed array size (int overflow and required capacity greater than the set maximum array size). In case of overflow, the new array size is the minimum required size; If it is larger than the set maximum size (MAX_ARRAY_SIZE), throw an exception if it is still larger than integer. MAX_VALUE, otherwise change the array size directly to integer. MAX_VALUE. (MAX_ARRAY_SIZE is 8 smaller than Integer.max_value).
2. add(int index, E element)
This method is used to add elements to the specified index. Parameter 1 is the index of the element to be added, and parameter 2 is the element to be added. Add (int index, E element)
Public void add(int index, E element) {rangeCheckForAdd(index); // Determine whether to expand ensureCapacityInternal(size + 1); // Increments modCount!! Arraycopy (elementData, index, elementData, index + 1, size-index); arrayCopy (elementData, index, elementData, index + 1, size-index); // Add element assignment to input index elementData[index] = element; // array size plus one size++; }Copy the codeCheck whether the index is valid by:
/** * A version of rangeCheck used by add and addAll. */ private void rangeCheckForAdd(int index) Exceeds the actual size (not capacity!) of the array There is also a rangeCheck() method in the ArrayList source code. It's a little bit different than that. if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }Copy the codeThe implementation of add(int index, E element) has one more step of the index validity bonus than add(E E), and requires the specified index and subsequent elements to be one bit after the assignment. The insertion position must be greater than or equal to 0 and less than or equal to the size of the array (equal to the size of the array is equal to add(E E)), so even if the array is actually larger than the input index, it will still throw an exception if the above conditions are not met.
3. addAll(Collection<? extends E> c)
This method adds the elements of the collection passed to the ArrayList and returns a value indicating whether more than zero elements were successfully added. Adding zero elements returns false.
/** * Appends all of the elements in the specified collection to the end of * this list, in the order that they are returned by the * specified collection's Iterator. The behavior of this operation is * undefined if the specified collection is modified while the operation * is in progress. (This implies that the behavior of this call is * undefined if the specified collection is this list, and this * list is nonempty.) * * @param c collection containing elements to be added to this list * @return <tt>true</tt> if this list changed as a result of the call * @throws NullPointerException if the specified collection is null */ public boolean addAll(Collection<? Extends E> c) {Object[] a = c.toarray (); int numNew = a.length; EnsureCapacityInternal (size + numNew); // Increments modCount // Copies all elements of a after elementData. Arraycopy (a, 0, elementData, size, numNew) // update size size += numNew; return numNew ! = 0; }Copy the code4. addAll(int index, Collection<? extends E> c)
This method adds the elements of the passed collection to the specified index and after.
/** * Inserts all of the elements in the specified collection into this * list, starting at the specified position. Shifts the element * currently at that position (if any) and any subsequent elements to * the right (increases their indices). The new elements will appear * in the list in the order that they are returned by the * specified collection's iterator. * * @param index index at which to insert the first element from the * specified collection * @param c collection containing elements to be added to this list * @return <tt>true</tt> if this list changed as a result of the call * @throws IndexOutOfBoundsException {@inheritDoc} * @throws NullPointerException if the specified collection is null */ public boolean addAll(int index, Collection<? Extends E> c) {extends E> c) {extends E> c) {extends E> c) {extends E> c) { Object[] a = c.toArray(); int numNew = a.length; EnsureCapacityInternal (size + numNew); // Increments modCount int numMoved = size - index; If (numMoved > 0) system. arrayCopy (elementData, index, elementData, index + numNew, numMoved); Arraycopy (a, 0, elementData, index, numNew); size += numNew; return numNew ! = 0; }Copy the code5. set(int index, E element)
This method is used to modify the value of an existing element in an array. Parameter 1 is used to modify the index of the element, and parameter 2 is the modified value. The method returns the original value. The set method does not make structural changes to the ArrayList, so it does not cause modCount to change the set(int index, E element)
/** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) {// rangeCheck(index); // Save the original value, here is a method called elementData E oldValue = elementData(index); ElementData [index] = element; return oldValue; }Copy the codeThe rangeCheck method, which is used in set, get, and remove:
/** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. */ private void rangeCheck(int index) { // For the set, GET, and remove methods, it is also not true that the index is equal to the array size. // The index should be between 0 and size-1. Incoming negative will not throw an exception, but will throw an exception when get the value (abnormal ArrayIndexOutOfBoundsException). // rangeCheckForAdd evaluates the value of the input, guessing for efficiency (?) if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }Copy the code6. get(int index)
This method gets the element at the specified index and takes the index.
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E Get (int index) {// rangeCheck(index); // return elementData(index); }Copy the code7. remove(int index)
This method removes the element at the specified index. The removed element is returned.
/** * 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 The was removed from the list * @ throws IndexOutOfBoundsException {@ inheritDoc} * / public E remove (int index) {/ / will be on Index To check rangeCheck(index); // Remove also makes structural changes to arrays, modCount++; // Record the removed element E oldValue = elementData(index); Int numMoved = size-index-1; 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 return oldValue; }Copy the code8. remove(Object o)
This method removes the specified element. The return value is Boolean, indicating whether the element was successfully removed
/** * 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 * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> 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 <tt>true</tt> if this list contained the specified element */ 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; If (o.equals(elementData[index])) {fastRemove(index); return true; } } return false; }Copy the codeFastRemove source code:
/* * Private remove method that skips bounds checking and does not * return the value removed. */ private void FastRemove (int index) {// same modCount++ as remove(int index); 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 }Copy the code9. removeRange(int fromIndex, int toIndex)
This method removes elements in the specified index range. This method is modified to protected. The specific range is [fromIndex, toIndex), which is an interval between closed on the left and open on the right.
/** * Removes from this list all of the elements whose index is between * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. * Shifts any succeeding elements to the left (reduces their index). * This call shortens the list by {@code (toIndex - fromIndex)} elements. * (If {@code toIndex==fromIndex}, this operation has no effect.) * * @throws IndexOutOfBoundsException if {@code fromIndex} or * {@code toIndex} is out of range * ({@code fromIndex < 0 || * fromIndex >= size() || * toIndex > size() || * toIndex < fromIndex}) */ protected Void removeRange(int fromIndex, int toIndex) {// modCount only adds modCount++ once; Int numMoved = size-toindex; Arraycopy (elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; }Copy the code10. removeAll(Collection<? > c) and retainAll (Collection <? > c)
The removeAll() method removes elements from all collections that exist in the ArrayList. RemoveAll (list2) removes 2, 4, 6, and 8 from list1. For example, list1 contains 10 elements from 0 to 9 and List2 contains 5 elements from 2, 4, 6, and 10. The retainAll() method computes the intersection of the two sets. These two methods are put together because their source code uses the same method. Source:
/** * Removes from this list all of its elements that are contained in the * specified collection. * * @param c collection containing elements to be removed from this list * @return {@code true} if this list changed as a result of the call * @throws ClassCastException if the class of an element of this list * is incompatible with the specified collection * (<a href="Collection.html#optional-restrictions">optional</a>) * @throws NullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">optional</a>), * or if the specified collection is null * @see Collection#contains(Object) */ public boolean removeAll(Collection<? > c) {// Check objects.requirenonnull (c); return batchRemove(c, false); } /** * Retains only the elements in this list that are contained in the * specified collection. In other words, removes from this list all * of its elements that are not contained in the specified collection. * * @param c collection containing elements to be retained in this list * @return {@code true} if this list changed as a result of the call * @throws ClassCastException if the class of an element of this list * is incompatible with the specified collection * (<a href="Collection.html#optional-restrictions">optional</a>) * @throws NullPointerException if this list contains a null element and the * specified collection does not permit null elements * (<a href="Collection.html#optional-restrictions">optional</a>), * or if the specified collection is null * @see Collection#contains(Object) */ public boolean retainAll(Collection<? > c) {// Check objects.requirenonnull (c); return batchRemove(c, true); }Copy the codebatchRemove(Collection<? > c, Boolean complement)
private boolean batchRemove(Collection<? > c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; Try {// complement is true, elementData is false, elementData is true, elementData is for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if C.contains () throws. // Normally, r == size, which indicates that the contains() method is abnormal. If (r! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // If complement is true, elementData stores the intersection of sets. // If complement is false, elementData stores elements left after subtracting. // w==size // set extra elements to null, modCount plus the number of elements set to null if (w! = size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; }} // Return modified to true, // ArrayList deletes elements // 2. ArrayList has an intersection with the incoming collection (the intersection length is less than size) // 3. ArrayList has no intersection with the incoming collection (the intersection length is 0) // When false, there are several possible cases: // 1. ArrayList does not delete elements // 2. The passed collection has the values of all the elements of the ArrayList collection (intersection length equals size) return modified; }Copy the codeThe core method of removeAll() and retainAll() is the batchRemove() method. The batchRemove() method determines what elements elementData should retain based on the passing in parameter complement. Preserves the element of the intersection, if false, preserves the element that should not be removed. The return value is validated against the length W of elementData.
11. clear()
This method empties all the elements in the ArrayList.
/** * Removes all of the elements from this list. The list will * be empty after this call returns. */ public void Clear () {// same structural change modCount++; // set null for (int I = 0; i < size; i++) elementData[i] = null; // size changes to 0 size = 0; }Copy the code12. indexOf(Object o)
This method is used to get the index position of the first occurrence of a given object in the ArrayList, and returns -1 if the specified object is not found.
/** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : O.quals (get(I)))</tt>, * or-1 if there is no such index. */ public int indexOf(Object o) { If (o == null) {for (int I = 0; i < size; i++) if (elementData[i]==null) return i; For (int I = 0; for (int I = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }Copy the codeNull is singled out because although Object can be null, null pointer exceptions are thrown before calling equals(), and equals() cannot be used.
13. lastIndexOf(Object o)
Gets the index of the last occurrence of the given object in the list, or -1 if it was not found.
/** * Returns the index of the last occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the highest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, */ if there is no such index. */ 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; }Copy the code14. trimToSize()
This method removes the reserved capacity and only preserves the space needed for the actual length of the array.
/** * Trims the capacity of this <tt>ArrayList</tt> instance to be the * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */ public void trimToSize() { modCount++; If (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the code15. clone()
This method clones an instance of ArrayList, noting that it is a shallow copy.
/** * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The * elements themselves are not copied.) * * @return a clone of this <tt>ArrayList</tt> instance * // Copy the original elements into the new ArrayList try {ArrayList<? > v = (ArrayList<? >) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); }}Copy the code16. WriteObeject (Java. IO. ObjectOutputStream s) and readObject (Java. IO. ObjectInputStream s)
Because elementData is decorated with the keyword TRANSIENT, the writeObject and readObject methods are used for serialization-related operations. Because of the size of the ArrayList, serializing elementData serializes a lot of NULL, so only the actual size of the array is actually serialized.
/** * Save the state of the <tt>ArrayList</tt> instance to a stream (that * is, serialize it). * * @serialData The length of the array backing the <tt>ArrayList</tt> * instance is emitted (int), followed by all of its elements * (each an <tt>Object</tt>) in the proper order. */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; // tranisent will serialize s.faultwriteObject (); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. i<size; i++) { s.writeObject(elementData[i]); } if (modCount ! = expectedModCount) { throw new ConcurrentModificationException(); }}Copy the code/** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); }}}Copy the code