One, foreword
Standing on the shoulders of giants, this series of Java Collections framework articles reference Skywang12345 – Java Collections series, really well spoken, can refer to. JDK 6.0 and JDK 8.0 have changed the collection framework quite a bit, so this series of articles is based on JDk_1.8.0_161.
Second, the introduction
Let’s start by looking at the class definition of ArrayList and its inheritance
java.util.Collection<E>
-> java.util.AbstractCollection<E>
-> java.util.AbstractList<E>
-> java.util.ArrayList<E>
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the codeAn ArrayList is an array queue, the equivalent of a dynamic array. Compared to arrays in Java, its size can grow dynamically. It inherits AbstractList and implements List, RandomAccess, Cloneable, java.io.Serializable interfaces.
- ArrayList inherits AbstractList and implements List. It is an array queue that provides related add, delete, modify, iterate, and so on.
- ArrayList implements the RandmoAccess interface, which provides random access. RandmoAccess is a Java implementation used by lists to provide fast access to lists. In an ArrayList, you can get an element object quickly by its ordinal number. That’s fast random access. Later, we’ll compare the efficiency of “fast random access” and “access through an Iterator” for lists.
- ArrayList implements the Cloneable interface, which overrides the clone() function and can be cloned.
- ArrayList implements the Java.io.Serializable interface, which means that ArrayList supports serialization and can be transmitted by serialization.
Let’s look at the relationship between ArrayList and Collection as a whole, as shown below:
ArrayList contains two important objects: elementData and Size. (1) elementData is an “array of type Object[]” that holds the elements added to the ArrayList. In fact, elementData is a dynamic array that we can execute using the constructor ArrayList(int initialCapacity). Its initialCapacity is initialCapacity; If an ArrayList is created through the constructor ArrayList() with no arguments, elementData defaults to an empty array. The size of the elementData array grows dynamically based on the size of the ArrayList, as shown in the ensureCapacity() function in source code analysis. (2) size is the actual size of the dynamic array.
Three, parsing,
The source code of the analysis, I personally like to see from the use of the method, rather than the source code all the way to see again, unless it is a relatively short source line, if it is thousands of lines of code, I think it will be very crashed. So not only learning efficiency, but also look at the source itself is a very boring thing, easy to look at don’t want to look down (big guy ignore), very hit the interest of learning source code.
1. To understand a class, the first thing we need to understand is its constructor. So let’s start with the constructor of an ArrayList. ArrayList has three constructors.
// The default ArrayList constructor. Set elementData to an empty array
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// ArrayList constructor with capacity size.
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// If initialCapacity is greater than 0, create an array
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// Initialize elementData to an empty array with initial capacity of 0
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}// Create an ArrayList containing the Collection
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// If the size of the ArrayList containing the Collection is not zero, copy the data to elementData
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// Otherwise, initialize an empty array
this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeSeveral fields appear in the constructor: elementData, EMPTY_ELEMENTDATA, DEFAULTCAPACITY_EMPTY_ELEMENTDATA, and so on, so let’s look at the definitions of these fields.
// Share an empty array instance.
private static final Object[] EMPTY_ELEMENTDATA = {};
// An instance of an empty array for sharing, initializes a default empty array, distinguished from EMPTY_ELEMENTDATA, so that you know how much to fill when adding the first element
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// For the above two empty arrays, it feels similar. As you can see from the three constructors, the no-argument constructor is used to create instances
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA, while the constructor with arguments uses EMPTY_ELEMENTDATA. In JDK 1.7 there was only EMPTY_ELEMENTDATA,
//JDK 1.8 uses DEFAULTCAPACITY_EMPTY_ELEMENTDATA instead of EMPTY_ELEMENTDATA. EMPTY_ELEMENTDATA is optimized for creating empty instances of ArrayList.
// Generate unnecessary empty arrays such that all empty instances of ArrayList point to the same empty array.
// The real array of ArrayList data
transient Object[] elementData;
Copy the codeArrayList = ArrayList = ArrayList = ArrayList = ArrayList = ArrayList = ArrayList = ArrayList = ArrayList = ArrayList = ArrayList ArrayList adds data in two ways.
// Add elements to the end of the ArrayList
public boolean add(E e) {
// The first time the element is added, size=0, so the argument passed is 1
ensureCapacityInternal(size + 1); // Increments modCount!!
// Place the added element at the end
elementData[size++] = e;
return true;
}
// Adds elements to the specified location of the ArrayList
public void add(int index, E element) {
// Check if index is out of bounds or valid
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// Copy data
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
/ / size + 1
size++;
}
private void ensureCapacityInternal(int minCapacity) {
// If the data is added for the first time, the calculateCapacity method returns 10, then the ensureExplicitCapacity method
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// Calculate the capacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// If elementData is an empty array, compare the maximum minCapacity passed in with DEFAULT_CAPACITY=10
Math.max(1,10) = 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// Number of changes +1
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// Get the current capacity of the elementData array, which is the length of the current array
int oldCapacity = elementData.length;
// The new capacity is: current capacity + current capacity /2 (that is, 1.5 times the original capacity)
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Copy the array to the new capacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeSize is the number of elements in the ArrayList. Add (E E) ¶ DEFAULT_CAPACITY specifies the default capacity of the ArrayList when the constructor without arguments is called. Here’s how to call the add method to add elements: EnsureCapacityInternal (add(int index, E Element)) when we call add(int index, E element) for the first time, we call ensureCapacityInternal (add(int index, E element)). There is also a data copy operation. EnsureCapacityInternal is a simple method that simply calls ensureExplicitCapacity. ③. The calculateCapacity method is called in the ensureExplicitCapacity method argument. ④ The calculateCapacity method first evaluates whether the elementData array is equal to DEFAULTCAPACITY_EMPTY_ELEMENTDATA, which is associated with calling the constructor with no arguments, and returns a default initial capacity of 10 if it is equal. EnsureExplicitCapacity = modCount +1 = modCount +1 = modCount +1 = modCount +1 = modCount +1 An if judgment, which must be true, is then called to grow, passing in the initial capacity of 10. 6. Enter the turns method, first will get the current capacity, and then declare a new capacity is the current capacity, coupled with the current capacity of half the value of this also means that when the ArrayList capacity is insufficient, will automatically capacity expansion to the original 1.5 times, the last call Arrays. The copyOf for a copy of the array elements, When we call the no-argument constructor, we initialize an array with a default size of 10 and expand it by 1.5 times the original size.
When we call add the second time, the real element of the array is only 1, size=1, and the array is 10, and the argument passed to ensureCapacityInternal is 2, so you can see for yourself what the logic is. You can also look at the logic of the add operation when other constructors are called. The addAll method, because it’s an added Collection, needs to convert the Collection to an array, and then adjust the size of the array, which is also called EnsurecapityInternal, which I won’t describe here.
3. Let’s look at deleting elements.
// Delete by subscript and return this element
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; // clear to let GC do its work
return oldValue;
}
// Delete 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; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
// If not removed
if (numMoved > 0)
// Array copy
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// Set the last item of the array to null, with length -1, so that the GC can do garbage collection
elementData[--size] = null; // clear to let GC do its work
}
// Delete data in batches based on the range
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.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;
}
// Delete according to a Collection
public boolean removeAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection<? > c,boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
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.
if(r ! = size) { System.arraycopy(elementData, r,elementData, w,size - r); w += size - r; }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;
}
Copy the codeRemoveAll (Collection
< p style = “margin-bottom: 0pt; margin-bottom: 0pt; Use remove(Object o) : ①. When o is null, it means that null can be added to an ArrayList. It then loops through the array and calls the fastRemove method, which determines whether the element has been deleted or not. If not, it copies the array first, empting the last element so that the GC can reclaim it. If o is not null, check whether o is equal to an element in the array. If o is equal to an element in the array, check whether o is equal to an element in the array. If o is not equal, check whether o is equal to an element in the array.
Remove (int index) : first check the subscript, then get the element of the subscript, and determine whether the element of the subscript has been removed, if not, then copy the array, then empty the last element of the array, size-1, and finally return the element of the subscript.
RemoveRange (int fromIndex, int toIndex) : First copy the range of data, then empty the array elements, and finally reassign the array length. In general, ArrayList deletion is relatively simple.
4. Continue with the get operations of ArrayList to get elements and the set operations to modify elements.
// Get the element by subscript
public E get(int index) {
// check if the subscript is out of bounds
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
// Return the element
return (E) elementData[index];
}
// Update a subscript element
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the codeAs you can see from the above code, getting and updating elements is not complicated. First, detect the subscript when retrieving the element, and then directly return the element in the array index position; Update data is also the first detection of the subscript, extract the current location of the element, and then directly replace the original element and return the old element.
For an ArrayList iteration, we can use: for, foreach, iterator. If the list data is modified, it can cause problems, or even crashes, as we often do.
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
for(String str : list) { System.out.println(str); }}}Copy the codeAfter compiling the class file using the command line javap -c -l main. class, we get the following contents from the main. class file. Can see in the use of a for loop is traversed, no call Iterator related method, so in a for loop to the operations such as add, delete, will not result in a ConcurrentModificationException exceptions, but will lead to other problems, here is not carried out; Iterator :()Ljava/util/ iterator; ()Ljava/util/ iterator; ()Ljava/util/ iterator; Traverse method, when we add/remove elements in the foreach traversal, can produce abnormal ConcurrentModificationException, can try. Of course directly using the iterator iterative modifying data at the same time, can also cause ConcurrentModificationException exception, the exception is related to we said before modCount.
C:\Users\Administrator\Desktop > Javap -c -l main. class Compiled from "main.java" public class Main {public Main(); Code: 0: aload_0 1: invokespecial #1 // Method java/lang/Object."<init>":()V 4: return LineNumberTable: line 4: 0 public static void main(java.lang.String[]); Code: 0: new #2 // class java/util/ArrayList 3: dup 4: invokespecial #3 // Method java/util/ArrayList."<init>":()V 7: astore_1 8: aload_1 9: ldc #4 // String a 11: invokeinterface #5, 2 // InterfaceMethod java/util/List.add:(Ljava/lang/Object;) Z 16: pop 17: aload_1 18: ldc #6 // String b 20: invokeinterface #5, 2 // InterfaceMethod java/util/List.add:(Ljava/lang/Object;) Z 25: pop 26: aload_1 27: ldc #7 // String c 29: invokeinterface #5, 2 // InterfaceMethod java/util/List.add:(Ljava/lang/Object;) Z 34: pop 35: iconst_0 36: istore_2 37: iload_2 38: aload_1 39: invokeinterface #8, 1 // InterfaceMethod java/util/List.size:()I 44: if_icmpge 69 47: getstatic #9 // Field java/lang/System.out:Ljava/io/PrintStream; 50: aload_1 51: iload_2 52: invokeinterface #10, 2 // InterfaceMethod java/util/List.get:(I)Ljava/lang/Object; 57: checkcast #11 // class java/lang/String 60: invokevirtual #12 // Method java/io/PrintStream.println:(Ljava/lang/String;) V 63: iinc 2, 1 66: goto 37 69: getstatic #9 // Field java/lang/System.out:Ljava/io/PrintStream; 72: ldc #13 // String ------------------------- 74: invokevirtual #12 // Method java/io/PrintStream.println:(Ljava/lang/String;) V 77: aload_1 78: invokeinterface #14, 1 // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator; 83: astore_2 84: aload_2 85: invokeinterface #15, 1 // InterfaceMethod java/util/Iterator.hasNext:()Z 90: ifeq 113 93: aload_2 94: invokeinterface #16, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object; 99: checkcast #11 // class java/lang/String 102: astore_3 103: getstatic #9 // Field java/lang/System.out:Ljava/io/PrintStream; 106: aload_3 107: invokevirtual #12 // Method java/io/PrintStream.println:(Ljava/lang/String;) V 110: goto 84 113: return }Copy the codeLet’s take a look at the iterator() method.
// The Itr object is returned directly
public Iterator<E> iterator(a) {
return new Itr();
}
//Itr implements the Iterator interface
private class Itr implements Iterator<E> {
// The index of the next element to return
int cursor;
int lastRet = -1;
ExpectedModCount is assigned here
int expectedModCount = modCount;
Itr() {}
// If the index of the next element is not equal to the length of the ArrayList, it does not point to the last element
public boolean hasNext(a) {
returncursor ! = size; }@SuppressWarnings("unchecked")
public E next(a) {
/ / ConcurrentModificationException anomaly detection
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];
}
// Delete elements
public void remove(a) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}final void checkForComodification(a) {
// An exception is thrown when modCount changes not as many times as expected.
// Add, remove, clear, etc
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
// omit other methods. }Copy the codeArrayList has an iterator dedicated to iteration — listIterator(). It has two overloaded methods. Both directly return a ListItr object.
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
public ListIterator<E> listIterator(a) {
return new ListItr(0);
}
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super(a); cursor = index; }// Does the previous element exist
public boolean hasPrevious(a) {
returncursor ! =0;
}
// Returns the index of the next element
public int nextIndex(a) {
return cursor;
}
// Returns the index of the previous element
public int previousIndex(a) {
return cursor - 1;
}
// Returns the previous element
@SuppressWarnings("unchecked")
public E previous(a) {
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];
}
// Update data
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}// Add data
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 newConcurrentModificationException(); }}}Copy the codeListItr inherits the Itr class and implements the ListIterator interface, which in turn inherits the Iterator interface. ListItr class has add, set, etc. This means that we can add and modify data at the same time as we iterate, and we can get the previous element, the index of the previous element, and we can delete and so on. So if we iterate through an ArrayList, You can use the listIterator() method.
6. ArrayList Other common methods.
// Query the subscript index of an element from the array header
public int indexOf(Object o) {
if (o == null) {
// If it is null, the index is returned after traversal
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// If it is not empty, the index is returned after traversing and determining whether it is equal
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
// If this element is not found, return -1
return -1;
}
// Returns whether the array contains an element, in which case indexOf is called
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// Query the subscript index of an element from the end of the array
public int lastIndexOf(Object o) {
if (o == null) {
// If it is null, the index will be returned after traversing from the end
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;
}
// If this element is not found, return -1
return -1;
}
// Clear the arraylist
public void clear(a) {
modCount++;
// Iterate through the array, null all elements, so that the GC can do garbage collection
for (int i = 0; i < size; i++)
elementData[i] = null;
// set the length to 0
size = 0;
}
// Check whether the list is an empty array
public boolean isEmpty(a) {
return size == 0;
}
Note that when this method is called to convert an ArrayList to an array, it may throw a ClassCastException
// Use the toArray(T[] a) method to convert to a specific type
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// To convert an ArrayList to an array, the code is simple: copy the data
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
Copy the codeThese are just a few of the common methods used in ArrayList. The rest of the methods are not explained, but you can check them out for yourself.
Four,
1. An ArrayList is actually a dynamic array that holds data. When we construct an ArrayList; Using the default constructor, ArrayList initializes the default capacity of 10 when data is first added. 2. When The capacity of ArrayList is insufficient to hold all elements, ArrayList resets the capacity: new capacity = original capacity + original capacity / 2. That is, 1.5 times the original capacity. ArrayList clones all elements into an array. 4. ArrayList implements java.io.Serializable. When writing to an output stream, write “capacity” first, then “each element”; When reading an input stream, read capacity first and then each element in turn. ArrayList is not thread-safe. We do not see any locks or synchronization blocks in the ArrayList method, so it is not thread-safe.
Five, the reference
ArrayList of Java Collection series 03 provides a detailed introduction (source code parsing) and usage examples